Combinatorial optimisation via highly efficient quantum walks
arXiv:1912.07353 · doi:10.1103/PhysRevResearch.2.023302
Abstract
We present a highly efficient quantum circuit for performing continuous time quantum walks (CTQWs) over an exponentially large set of combinatorial objects, provided that the objects can be indexed efficiently. CTQWs form the core mixing operation of a generalised version of the Quantum Approximate Optimisation Algorithm, which works by `steering' the quantum amplitude into high-quality solutions. The efficient quantum circuit holds the promise of finding high-quality solutions to certain classes of NP-hard combinatorial problems such as the Travelling Salesman Problem, maximum set splitting, graph partitioning, and lattice path optimisation.
arXiv comment8 pages, 8 figures
References in corpus (23)
- Quantum random walks - an introductory overview
- Quantum Computation and Decision Trees
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Spatial search by quantum walk
- Large-scale silicon quantum photonics implementing arbitrary two-qubit processing
- Quantum transport simulations in a programmable nanophotonic processor
- Universal computation by multi-particle quantum walk
- A 2D Quantum Walk Simulation of Two-Particle Dynamics
- Quantum advantage with shallow circuits
- Microscopy of the interacting Harper-Hofstadter model in the few-body limit
- -mixers: analytical and numerical results for QAOA
- Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians
- Experimental Quantum Fast Hitting on Hexagonal Graphs
- Classical approach to the graph isomorphism problem using quantum walks
- Efficient Quantum Walk on a Quantum Processor
- Quantum walk-based search and centrality
- Quantum Fourier Transform in Computational Basis
- A quantum walk assisted approximate algorithm for bounded NP optimisation problems
- Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
- Finding spin-glass ground states using quantum walks
- Quantum topology identification with deep neural networks and quantum walks
- Quantum centrality testing on directed graphs via PT-symmetric quantum walks
- Quantum search on structured problems
Cited by in corpus (20)
- Quantum walk-based portfolio optimisation
- Review on Quantum Walk Computing: Theory, Implementation, and Application
- Constrained Optimization via Quantum Zeno Dynamics
- Feedback-assisted quantum search by continuous-time quantum walks
- Deterministic spatial search using alternating quantum walks
- Defining Quantum Games
- QSW_MPI: a framework for parallel simulation of quantum stochastic walks
- Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs
- Estimating Gibbs partition function with quantumClifford sampling
- Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer
- Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems
- A framework for optimal quantum spatial search using alternating phase-walks
- LX-mixers for QAOA: Optimal mixers restricted to subspaces and the stabilizer formalism
- Citizen Science Games on the Timeline of Quantum Games
- QuOp_MPI: a framework for parallel simulation of quantum variational algorithms
- Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
- Recurrence in discrete-time quantum stochastic walks
- Quantum search by continuous-time quantum walk on t-designs
- Q-CHOP: Quantum constrained Hamiltonian optimization
- Variational Quantum Algorithm for Constrained Combinatorial Optimization Problems