Finding spin-glass ground states using quantum walks
arXiv:1903.05003 · doi:10.1088/1367-2630/ab5ca2
Abstract
Quantum computation using continuous-time evolution under a natural hardware Hamiltonian is a promising near- and mid-term direction toward powerful quantum computing hardware. We investigate the performance of continuous-time quantum walks as a tool for finding spin glass ground states, a problem that serves as a useful model for realistic optimization problems. By performing detailed numerics, we uncover significant ways in which solving spin glass problems differs from applying quantum walks to the search problem. Importantly, unlike for the search problem, parameters such as the hopping rate of the quantum walk do not need to be set precisely for the spin glass ground state problem. Heuristic values of the hopping rate determined from the energy scales in the problem Hamiltonian are sufficient for obtaining a better than square-root scaling. This makes it practical to use quantum walks for solving such problems, and opens the door for a range of applications on suitable quantum hardware.
arXiv comment32 pages, 11 figures
References in corpus (41)
- Probing many-body dynamics on a 51-atom quantum simulator
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Strengths and Weaknesses of Quantum Computing
- Quantum Computation and Decision Trees
- A Quantum Random Walk Search Algorithm
- Exponential algorithmic speedup by quantum walk
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Spatial search by quantum walk
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Quantum Boltzmann Machine
- Experimental signature of programmable quantum annealing
- A practical scheme for quantum computation with any two-qubit entangling gate
- Fixed-point quantum search with an optimal number of queries
- Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
- Absence of an Almeida-Thouless line in Three-Dimensional Spin Glasses
- Power of Pausing: Advancing Understanding of Thermalization in Experimental Quantum Annealers
- Simple universal models capture all classical spin physics
- Reverse annealing for the fully connected -spin model
- Experimental determination of Ramsey numbers
- Modernizing Quantum Annealing using Local Searches
- Perturbative Gadgets at Arbitrary Orders
- Circuit design for multi-body interactions in superconducting quantum annealing system with applications to a scalable architecture
- Spin glasses in a field: Three and four dimensions as seen from one space dimension
- A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera Graph
- Improving quantum annealing of the ferromagnetic -spin model through pausing
- A quantum walk assisted approximate algorithm for bounded NP optimisation problems
- Quantum annealing with longitudinal bias fields
- Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
- Quantum algorithm for energy matching in hard optimization problems
- Quantum speedup of the Travelling Salesman Problem for bounded-degree graphs
- Finding spin-glass ground states using quantum walks
- Stability of the quantum Sherrington-Kirkpatrick spin glass model
- Fixed-Point Adiabatic Quantum Search
- Equation Planting: A Tool for Benchmarking Ising Machines
- Practical designs for permutation symmetric problem Hamiltonians on hypercubes
- Continuous-Time Quantum Algorithms for Unstructured Problems
- Hybrid annealing using a quantum simulator coupled to a classical computer
- Duality in Quantum Quenches and Classical Approximation Algorithms: Pretty Good or Very Bad
- Nonlinear susceptibility of a quantum spin glass under uniform transverse and random longitudinal magnetic fields
Cited by in corpus (33)
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- Quantum-enhanced Markov chain Monte Carlo
- Quantum speedup of branch-and-bound algorithms
- Quantum variational optimization: The role of entanglement and problem hardness
- Combinatorial optimisation via highly efficient quantum walks
- Finding spin-glass ground states using quantum walks
- On the optimality of spatial search by continuous-time quantum walk
- Challenges of variational quantum optimization with measurement shot noise
- An energetic perspective on rapid quenches in quantum annealing
- Finding a marked node on any graph by continuous-time quantum walk
- Two quantum Ising algorithms for the Shortest Vector Problem: one for now and one for later
- Approximating the quantum approximate optimization algorithm with digital-analog interactions
- Quantum algorithms for scientific computing
- Feedback-assisted quantum search by continuous-time quantum walks
- Guided quantum walk
- Fluctuation guided search in quantum annealing
- Continuous-time quantum walks for MAX-CUT are hot
- Improved Upper Bounds for the Hitting Times of Quantum Walks
- Optimizing the spatial spread of a quantum walk
- How to Compute Using Quantum Walks
- Problem-Size Independent Angles for a Grover-Driven Quantum Approximate Optimization Algorithm
- 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
- Continuous-time quantum optimisation without the adiabatic principle
- Using copies to improve precision in continuous-time quantum computing
- Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
- A thermodynamic approach to optimization in complex quantum systems
- Unstructured Adiabatic Quantum Optimization: Optimality with Limitations
- Quantum Hopfield Model with Dilute Memories
- Improving success probability in the LHZ parity embedding by computing with quantum walks
- Quantum annealing and condensed matter physics