A quantum walk-assisted approximate algorithm for bounded NP optimisation problems
From MaRDI portal
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)
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.
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
Cites work
- scientific article; zbMATH DE number 5899272 (Why is no real title available?)
- scientific article; zbMATH DE number 3150484 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 751135 (Why is no real title available?)
- scientific article; zbMATH DE number 1877046 (Why is no real title available?)
- A Simplex Method for Function Minimization
- A theory of measurement in diagnosis from first principles
- Adiabatic quantum state generation and statistical zero knowledge
- An analytical study of quantum walk through glued-tree graphs
- Comparing classical and quantum pageranks
- Efficient quantum circuits for diagonal unitaries without ancillas
- Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries
- Exponential algorithmic speedup by a quantum walk
- From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
- Physical implementation of quantum walks
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Reducibility among combinatorial problems
- Some better bounds on the variance with applications
- State transfer on graphs
- Strong lower bounds on the approximability of some NPO PB-complete maximization problems
- The fundamental limit theorems in probability
- Universal computation by multiparticle quantum walk
Cited in
(15)- Discrete-time quantum walk-based optimization algorithm
- Quantum approximate optimization for combinatorial problems with constraints
- 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
- A study of the performance of classical minimizers in the quantum approximate optimization algorithm
- Optimizing the walk coin in the quantum random walk search 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
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)
