A quantum walk-assisted approximate algorithm for bounded NP optimisation problems

DOI10.1007/S11128-019-2171-3zbMATH Open1417.81095arXiv1804.08227OpenAlexW2963300030WikidataQ128578232 ScholiaQ128578232MaRDI QIDQ669949FDOQ669949

Authors: Juan-Miguel Gracia 

Publication date: 15 March 2019

Published in: Quantum Information Processing (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1804.08227

Recommendations

• Lower bounds on circuit depth of the quantum approximate optimization algorithm
• A study of the performance of classical minimizers in the quantum approximate optimization algorithm
• Quantum optimization
• Empirical performance bounds for quantum approximate optimization
• Quantum annealing learning search for solving QUBO problems

zbMATH Keywords

quantum walksminimum vertex coverQAOAquantum optimisation

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Sums of independent random variables; random walks (60G50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Quantum stochastic calculus (81S25)

Cites Work

• A Simplex Method for Function Minimization
• Title not available (Why is that?)
• Adiabatic quantum state generation and statistical zero knowledge
• Exponential algorithmic speedup by a quantum walk
• Title not available (Why is that?)
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Physical implementation of quantum walks
• Title not available (Why is that?)
• State transfer on graphs
• A theory of measurement in diagnosis from first principles
• Strong lower bounds on the approximability of some NPO PB-complete maximization problems
• Title not available (Why is that?)
• Universal computation by multiparticle quantum walk
• An analytical study of quantum walk through glued-tree graphs
• Title not available (Why is that?)
• Reducibility among combinatorial problems
• Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
• Comparing classical and quantum pageranks
• From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
• Some better bounds on the variance with applications
• Efficient quantum circuits for diagonal unitaries without ancillas
• The fundamental limit theorems in probability

Cited In (15)

• Quantum walk and its application domains: a systematic review
• Models in quantum computing: a systematic review
• Lower bounds on circuit depth of the quantum approximate optimization algorithm
• Using an \(A^\ast\)-based framework for decomposing combinatorial optimization problems to employ NISQ computers
• A quantum blockchain-enabled framework for secure private electronic medical records in Internet of medical things
• From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
• QSW\_MPI: a framework for parallel simulation of quantum stochastic walks
• Quantum semi-trust evaluation model with graph-based quantum walk teleportation
• Optimizing the walk coin in the quantum random walk search algorithm
• A study of the performance of classical minimizers in the quantum approximate optimization algorithm
• On the universality of the quantum approximate optimization algorithm
• A systematic method to building Dirac quantum walks coupled to electromagnetic fields
• One-dimensional quantum walks with two-step memory
• Discrete-time quantum walk-based optimization algorithm
• Quantum approximate optimization for combinatorial problems with constraints

Uses Software

• Cirq
• GitHub

This page was built for publication: A quantum walk-assisted approximate algorithm for bounded NP optimisation problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q669949)