Wong, TG;
Wunscher, K;
Lockhart, J;
Severini, S;
(2018)
Quantum walk search on Kronecker graphs.
Physical Review A
, 98
(1)
10.1103/PhysRevA.98.012338.
Preview |
Text
PhysRevA.98.012338.pdf - Published Version Download (472kB) | Preview |
Abstract
Kronecker graphs, obtained by repeatedly performing the Kronecker product of the adjacency matrix of an “initiator” graph with itself, have risen in popularity in network science due to their ability to generate complex networks with real-world properties. We explore spatial search by continuous-time quantum walk on Kronecker graphs. Specifically, we give analytical proofs for quantum search on first-, second-, and third-order Kronecker graphs with the complete graph as the initiator, showing that search takes Grover's O(√N) time. Numerical simulations indicate that higher-order Kronecker graphs with the complete initiator also support optimal quantum search.
| Type: | Article |
|---|---|
| Title: | Quantum walk search on Kronecker graphs |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1103/PhysRevA.98.012338 |
| Publisher version: | https://doi.org/10.1103/PhysRevA.98.012338 |
| Language: | English |
| Additional information: | This version is the version of the record. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Network formation & growth, Network searches, Nonlinear quantum walk, Quantum algorithms, Quantum Information, Networks |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10065152 |
Archive Staff Only
 |
View Item |
