A quantum walk assisted approximate algorithm for bounded NP optimisation problems

Abstract

This paper describes an application of the Quantum Approximate Optimisation Algorithm (QAOA) to efficiently find approximate solutions for computational problems contained in the polynomially bounded NP optimisation complexity class (NPO PB). We consider a generalisation of the QAOA state evolution to alternating quantum walks and solution-quality-dependent phase shifts, and use the quantum walks to integrate the problem constraints of NPO problems. We apply the recent concept of a hybrid quantum-classical variational scheme to attempt finding the highest expectation value, which contains a high-quality solution. The algorithm is applied to the problem of minimum vertex cover, showing promising results using only a fixed and low number of optimisation parameters.

References in corpus (4)

• Exponential algorithmic speedup by quantum walk
• Spatial search by quantum walk
• Universal computation by multi-particle quantum walk
• Centrality measure based on continuous-time quantum walks and experimental realization

Cited by in corpus (20)

• Domain wall encoding of discrete variables for quantum annealing and QAOA
• On the Universality of the Quantum Approximate Optimization Algorithm
• Review on Quantum Walk Computing: Theory, Implementation, and Application
• Combinatorial optimisation via highly efficient quantum walks
• Finding spin-glass ground states using quantum walks
• Constrained Optimization via Quantum Zeno Dynamics
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• Analytical Framework for Quantum Alternating Operator Ansätze
• Reachability Deficits in Quantum Approximate Optimization of Graph Problems
• Quantum Optimization for Training Quantum Neural Networks
• Hybrid Quantum-Classical Heuristic for the Bin Packing Problem
• Deterministic spatial search using alternating quantum walks
• QSW_MPI: a framework for parallel simulation of quantum stochastic walks
• Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer
• A framework for optimal quantum spatial search using alternating phase-walks
• 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
• Q-CHOP: Quantum constrained Hamiltonian optimization
• Interference and Measurement: Changing amplitude phase information to amplitude magnitude information
• Variational Quantum Algorithm for Constrained Combinatorial Optimization Problems