Quantum walk for community clique detection
A method of detecting cliques in a graph includes determining, based on a number of nodes in the graph, a number of qubits to be included in a quantum processor. The method includes assigning to each node in the graph, a qubit of the quantum processor. The method includes operating on the qubits with a preparation circuit to create a quantum state in the qubits that corresponds to the graph. The method includes operating on the quantum state with a random walk circuit, and measuring the qubits of the quantum processor to detect cliques in the graph. The preparation circuit comprises a plurality of single- and two-qubit operators, wherein, for each pair of adjacent nodes in the graph, an operator of the plurality of two-qubit operators acts on a pair of qubits corresponding to the pair of adjacent nodes to create the quantum state.
1. A method of detecting cliques in a graph, comprising:
determining, based on a number of nodes in said graph, a number of qubits to be included in a quantum processor;
assigning to each node in said graph, a qubit of said quantum processor having said determined number of qubits;
operating on said qubits of said quantum processor with a preparation circuit to create a quantum state in said qubits that corresponds to said graph;
operating on said quantum state in said qubits with a random walk circuit; and
measuring said qubits of said quantum processor to detect cliques in said graph based on said operating with said random walk circuit,
wherein said preparation circuit comprises a plurality of single- and two-qubit operators, wherein, for each pair of adjacent nodes in said graph, an operator of said plurality of two-qubit operators acts on a pair of qubits corresponding to said pair of adjacent nodes to create said quantum state.
2. The method according to claim 1 , wherein said operator of said plurality of two-qubit operators acts on said pair of qubits corresponding to said pair of adjacent nodes to create said quantum state by flipping a parity of said pair of qubits.
3. The method according to claim 1 , wherein said random walk circuit comprises a coin operator and a step operator.
4. The method according to claim 3 , wherein said coin operator is a biased coin operator.
5. The method according to claim 3 , wherein said coin operator is an unbiased coin operator.
6. The method according to claim 3 , wherein said step operator is a conditional operator that changes a position state of the quantum state.
7. The method according to claim 3 , wherein eigenvalues of higher powers of said coin operator and said step operator provide a measure of self-cliques.
8. The method according to claim 1 , wherein said random walk circuit comprises a pair of operators that are repeated to evaluate a plurality of paths through the graph in parallel.
9. The method according to claim 8 , wherein said paths are different routes that can be traversed on said graph.
10. The method according to claim 9 , wherein a number of times that the pair of operators is repeated depends on a diameter of said graph.
11. A quantum processor for detecting cliques in a graph, comprising:
a number of qubits equal to a number of nodes in said graph, wherein each qubit corresponds to a node in said graph;
a quantum preparation circuit configured to prepare said qubits of said quantum processor in a quantum state corresponding to said graph, said quantum preparation circuit comprising a plurality of two-qubit operators;
a random walk circuit configured to operate on said qubits prepared in said quantum state; and
a measurement circuit configured to measure said qubits of said quantum processor to provide an indication of cliques in said graph,
wherein, for each pair of adjacent nodes of said graph, a two-qubit operator of said plurality of two-qubit operators is configured to operate on a pair of qubits corresponding to said pair of adjacent nodes to create said quantum state.
12. The quantum processor according to claim 11 , wherein said operator of said plurality of two-qubit operators acts on said pair of qubits corresponding to said pair of adjacent nodes to create said quantum state by flipping a parity of said pair of qubits.
13. The quantum processor according to claim 11 , wherein said random walk circuit comprises a coin operator and a step operator.
14. The quantum processor according to claim 13 , wherein said coin operator is a biased coin operator.
15. The quantum processor according to claim 13 , wherein said coin operator is an unbiased coin operator.
16. The quantum processor according to claim 13 , wherein said step operator is a conditional operator that changes a position state of the quantum state.
17. The quantum processor according to claim 13 , wherein eigenvalues of higher powers of said coin operator and said step operator provide a measure of self-cliques.
18. The quantum processor according to claim 11 , wherein said random walk circuit comprises a pair of operators that are repeated to evaluate a plurality of paths through the graph in parallel.
19. The quantum processor according to claim 18 , wherein said paths are different routes that can be traversed on said graph.
20. The quantum processor according to claim 19 , wherein a number of times that the pair of operators is repeated depends on a diameter of said graph.