Deriving Grover's lower bound from simple physical principles
Grover's algorithm constitutes the optimal quantum solution to the search problem and provides a quadratic speed-up over all possible classical search algorithms. Quantum interference between computational paths has been posited as a key resource behind this computational speed-up. However ther...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IOP Publishing
2016-01-01
|
| Series: | New Journal of Physics |
| Subjects: | |
| Online Access: | https://doi.org/10.1088/1367-2630/18/9/093047 |
| _version_ | 1797750962939494400 |
|---|---|
| author | Ciarán M Lee John H Selby |
| author_facet | Ciarán M Lee John H Selby |
| author_sort | Ciarán M Lee |
| collection | DOAJ |
| description | Grover's algorithm constitutes the optimal quantum solution to the search problem and provides a quadratic speed-up over all possible classical search algorithms. Quantum interference between computational paths has been posited as a key resource behind this computational speed-up. However there is a limit to this interference, at most pairs of paths can ever interact in a fundamental way. Could more interference imply more computational power? Sorkin has defined a hierarchy of possible interference behaviours—currently under experimental investigation—where classical theory is at the first level of the hierarchy and quantum theory belongs to the second. Informally, the order in the hierarchy corresponds to the number of paths that have an irreducible interaction in a multi-slit experiment. In this work, we consider how Grover's speed-up depends on the order of interference in a theory. Surprisingly, we show that the quadratic lower bound holds regardless of the order of interference. Thus, at least from the point of view of the search problem, post-quantum interference does not imply a computational speed-up over quantum theory. |
| first_indexed | 2024-03-12T16:40:26Z |
| format | Article |
| id | doaj.art-5b0950459d2945e287df5e62b7ded692 |
| institution | Directory Open Access Journal |
| issn | 1367-2630 |
| language | English |
| last_indexed | 2024-03-12T16:40:26Z |
| publishDate | 2016-01-01 |
| publisher | IOP Publishing |
| record_format | Article |
| series | New Journal of Physics |
| spelling | doaj.art-5b0950459d2945e287df5e62b7ded6922023-08-08T14:32:01ZengIOP PublishingNew Journal of Physics1367-26302016-01-0118909304710.1088/1367-2630/18/9/093047Deriving Grover's lower bound from simple physical principlesCiarán M Lee0John H Selby1University of Oxford , Department of Computer Science, Wolfson Building, Parks Road, Oxford OX1 3QD, UKUniversity of Oxford , Department of Computer Science, Wolfson Building, Parks Road, Oxford OX1 3QD, UK; Imperial College London , London SW7 2AZ, UKGrover's algorithm constitutes the optimal quantum solution to the search problem and provides a quadratic speed-up over all possible classical search algorithms. Quantum interference between computational paths has been posited as a key resource behind this computational speed-up. However there is a limit to this interference, at most pairs of paths can ever interact in a fundamental way. Could more interference imply more computational power? Sorkin has defined a hierarchy of possible interference behaviours—currently under experimental investigation—where classical theory is at the first level of the hierarchy and quantum theory belongs to the second. Informally, the order in the hierarchy corresponds to the number of paths that have an irreducible interaction in a multi-slit experiment. In this work, we consider how Grover's speed-up depends on the order of interference in a theory. Surprisingly, we show that the quadratic lower bound holds regardless of the order of interference. Thus, at least from the point of view of the search problem, post-quantum interference does not imply a computational speed-up over quantum theory.https://doi.org/10.1088/1367-2630/18/9/093047generalised probabilistic theorieshigher-order interferencequantum computing |
| spellingShingle | Ciarán M Lee John H Selby Deriving Grover's lower bound from simple physical principles New Journal of Physics generalised probabilistic theories higher-order interference quantum computing |
| title | Deriving Grover's lower bound from simple physical principles |
| title_full | Deriving Grover's lower bound from simple physical principles |
| title_fullStr | Deriving Grover's lower bound from simple physical principles |
| title_full_unstemmed | Deriving Grover's lower bound from simple physical principles |
| title_short | Deriving Grover's lower bound from simple physical principles |
| title_sort | deriving grover s lower bound from simple physical principles |
| topic | generalised probabilistic theories higher-order interference quantum computing |
| url | https://doi.org/10.1088/1367-2630/18/9/093047 |
| work_keys_str_mv | AT ciaranmlee derivinggroverslowerboundfromsimplephysicalprinciples AT johnhselby derivinggroverslowerboundfromsimplephysicalprinciples |