Period Finding with Adiabatic Quantum Computation
arXiv:1307.6538 · doi:10.1209/0295-5075/105/50005
Abstract
We outline an efficient quantum-adiabatic algorithm that solves Simon's problem, in which one has to determine the `period', or xor-mask, of a given black-box function. We show that the proposed algorithm is exponentially faster than its classical counterpart and has the same complexity as the corresponding circuit-based algorithm. Together with other related studies, this result supports a conjecture that the complexity of adiabatic quantum computation is equivalent to the circuit-based computational model in a stronger sense than the well-known, proven polynomial equivalence between the two paradigms. We also discuss the importance of the algorithm and its theoretical and experimental implications for the existence of an adiabatic version of Shor's integer factorization algorithm that would have the same complexity as the original algorithm.
6 pages
References in corpus (8)
- Bounds for the adiabatic approximation with applications to quantum computation
- Simple proof of equivalence between adiabatic quantum computation and the circuit model
- Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
- The Hidden Subgroup Problem - Review and Open Problems
- Tunneling spectroscopy using a probe qubit
- Excitation Gap from Optimized Correlation Functions in Quantum Monte Carlo Simulations
- Continuous-Time Quantum Algorithms for Unstructured Problems
- How Fast Can Quantum Annealers Count?
Cited by in corpus (16)
- Adiabatic Quantum Computing
- Quantum information processing with superconducting circuits: a review
- Nested Quantum Annealing Correction
- Quantum Gates with Controlled Adiabatic Evolutions
- Analog Nature of Quantum Adiabatic Unstructured Search
- Quantum Annealing - Foundations and Frontiers
- Improved Bounds for Eigenpath Traversal
- How Fast Can Quantum Annealers Count?
- Robust Diabatic Quantum Search by Landau-Zener-Stückelberg Oscillations
- Topologically protected Grover's oracle for the partition problem
- Lower bounds for adiabatic quantum algorithms by quantum speed limits
- Error-run-time trade-off in the adiabatic approximation beyond scaling relations
- Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation
- Simon's Period Finding on a Quantum Annealer
- More period finding with adiabatic quantum computation
- Improving adiabatic quantum factorization via chopped random-basis optimization