Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
arXiv:1709.00371 · doi:10.1103/PhysRevA.99.022339
Abstract
Computing using a continuous-time evolution, based on the natural interaction Hamiltonian of the quantum computer hardware, is a promising route to building useful quantum computers in the near-term. Adiabatic quantum computing, quantum annealing, computation by continuous-time quantum walk, and special purpose quantum simulators all use this strategy. In this work, we carry out a detailed examination of adiabatic and quantum walk implementation of the quantum search algorithm, using the more physically realistic hypercube connectivity, rather than the complete graph, for our base Hamiltonian. We calculate the optimal adiabatic schedule for the hypercube, and then interpolate between adiabatic and quantum walk searching, obtaining a family of hybrid algorithms. We show that all of these hybrid algorithms provide the quadratic quantum speed up when run with optimal parameter settings, which we determine and discuss in detail. We incorporate the effects of multiple runs of the same algorithm, noise applied to the qubits, and two types of problem misspecification, determining the optimal hybrid algorithm for each case. Our results reveal a rich structure of how these different computational mechanisms operate and should be balanced in different scenarios. For large systems with low noise and good control, quantum walk is the best choice, while hybrid strategies can mitigate the effects of many shortcomings in hardware and problem misspecification.
arXiv comment23 pages, 19 figures, RevTeX two-column, V3 revised section 'Noisy quantum searching', to appear in PRA
References in corpus (48)
- Quantum Mechanics helps in searching for a needle in a haystack
- Quantum Simulation
- A Quantum Approximate Optimization Algorithm
- Adiabatic Quantum Computing
- Strengths and Weaknesses of Quantum Computing
- A Quantum Random Walk Search Algorithm
- Spatial search by quantum walk
- Quantum Search by Local Adiabatic Evolution
- Quantum Computation by Adiabatic Evolution
- Quantum Boltzmann Machine
- Search via Quantum Walk
- What is the Computational Value of Finite Range Tunneling?
- Computational Role of Multiqubit Tunneling in a Quantum Annealer
- Fixed-point quantum search with an optimal number of queries
- Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning
- Model for l/f Flux Noise in SQUIDs and Qubits
- Entanglement in a quantum annealing processor
- Quantum Adiabatic Brachistochrone
- Spatial search by quantum walk is optimal for almost all graphs
- Optimizing Variational Quantum Algorithms using Pontryagin's Minimum Principle
- Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
- Near-optimal quantum circuit for Grover's unstructured search using a transverse field
- Towards quantum simulation with circular Rydberg atoms
- A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
- Quantum-Assisted Learning of Hardware-Embedded Probabilistic Graphical Models
- Experimental determination of Ramsey numbers
- Quantum speedup of classical mixing processes
- Quantum search by measurement
- Tunneling and speedup in quantum optimization for permutation-symmetric problems
- Accuracy vs run time in adiabatic quantum search
- Improved Error-Scaling for Adiabatic Quantum State Transfer
- Decoherence in Quantum Walks on the Hypercube
- Adiabatic quantum optimization with the wrong Hamiltonian
- A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera Graph
- Maximum-Entropy Inference with a Programmable Annealer
- Quantum search algorithms on the hypercube
- Adiabatic Quantum Search in Open Systems
- Fixed-Point Adiabatic Quantum Search
- Effects of dissipation in an adiabatic quantum search algorithm
- On The Power Of Coherently Controlled Quantum Adiabatic Evolutions
- Optimal computation with non-unitary quantum walks
- Dynamics of the quantum search and quench-induced first-order phase transitions
- Practical designs for permutation symmetric problem Hamiltonians on hypercubes
- High-fidelity adiabatic quantum computation using the intrinsic Hamiltonian of a spin system: Application to the experimental factorization of 291311
- Irreconcilable Difference Between Quantum Walks and Adiabatic Quantum Computing
- When Diabatic Trumps Adiabatic in Quantum Optimization
- The quantum walk search algorithm: Factors affecting efficiency
- Postprocessing can speed up general quantum search algorithms
Cited by in corpus (29)
- Scaling advantage in quantum simulation of geometrically frustrated magnets
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- Improving quantum annealing of the ferromagnetic -spin model through pausing
- Combinatorial optimisation via highly efficient quantum walks
- Finding spin-glass ground states using quantum walks
- An energetic perspective on rapid quenches in quantum annealing
- Approximating the quantum approximate optimization algorithm with digital-analog interactions
- Practical designs for permutation symmetric problem Hamiltonians on hypercubes
- Quantum Optimization for Training Quantum Neural Networks
- Guided quantum walk
- Scattering as a quantum metrology problem: a quantum walk approach
- Problem-Size Independent Angles for a Grover-Driven Quantum Approximate Optimization Algorithm
- How to Compute Using Quantum Walks
- Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms
- The quantum annealing gap and quench dynamics in the exact cover problem
- Rapid quantum approaches for combinatorial optimisation inspired by optimal state-transfer
- Grover Speedup from Many Forms of the Zeno Effect
- Noise-tolerant quantum speedups in quantum annealing without fine tuning
- Robust Diabatic Quantum Search by Landau-Zener-Stückelberg Oscillations
- Depth scaling of unstructured search via quantum approximate optimization
- Using copies to improve precision in continuous-time quantum computing
- A thermodynamic approach to optimization in complex quantum systems
- Quantum spatial search with electric potential : long-time dynamics and robustness to noise
- Entropy Computing, A Paradigm for Optimization in Open Photonic Systems
- Performance of Domain-Wall Encoding for Quantum Annealing
- Recurrence in discrete-time quantum stochastic walks
- Improving success probability in the LHZ parity embedding by computing with quantum walks
- Explicitly Quantum-parallel Computation by Displacements
- Quantum annealing and condensed matter physics