From the quantum approximate optimization algorithm to a quantum alternating operator ansatz

DOI10.3390/a12020034zbMath1461.68085arXiv1709.03489OpenAlexW2754868542WikidataQ128369780 ScholiaQ128369780MaRDI QIDQ2632506

Rupak Biswas, Davide Venturelli, Zhihui Wang, Stuart Hadfield, Bryan O'Gorman, Eleanor G. Rieffel

Publication date: 14 May 2019

Published in: Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

optimizationconstrained optimizationquantum algorithmsapproximate optimizationquantum computingconstraint satisfaction problemsquantum circuit ansatzquantum gate model

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum gates (81P65)

Related Items (20)

Leveraging special-purpose hardware for local search heuristics ⋮ Using an \(A^\ast\)-based framework for decomposing combinatorial optimization problems to employ NISQ computers ⋮ An introduction to variational quantum algorithms for combinatorial optimization problems ⋮ A practitioner’s guide to quantum algorithms for optimisation problems ⋮ Quantum alternating operator ansatz for solving the minimum exact cover problem ⋮ Benchmarking the quantum approximate optimization algorithm ⋮ On the universality of the quantum approximate optimization algorithm ⋮ Efficient quantum feature extraction for CNN-based learning ⋮ Solving the Kemeny ranking aggregation problem with quantum optimization algorithms ⋮ Preparing a Fast Pauli Decomposition for Variational Quantum Solving Linear Equations ⋮ Benchmarking the performance of portfolio optimization with QAOA ⋮ Locating quantum critical points with shallow quantum circuits ⋮ A universal quantum algorithm for weighted maximum cut and Ising problems ⋮ Solving MaxCut with quantum imaginary time evolution ⋮ A direct error correction method for quantum machine learning ⋮ A quantum walk-assisted approximate algorithm for bounded NP optimisation problems ⋮ Variational Quantum Eigensolver and Its Applications ⋮ A conditional generative model based on quantum circuit and classical optimization ⋮ Classical symmetries and the quantum approximate optimization algorithm ⋮ Unconstrained binary models of the travelling salesman problem variants for quantum optimization

Cites Work

• Better approximation algorithms for \textsc{Set Splitting} and \textsc{Not-All-Equal Sat}
• Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
• A quantum walk-assisted approximate algorithm for bounded NP optimisation problems
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• On the hardness of approximating minimum vertex cover
• Optimization, approximation, and complexity classes
• Approximating maximum independent sets by excluding subgraphs
• Quantifiers and approximation
• A still better performance guarantee for approximate graph coloring
• On dependent randomized rounding algorithms
• The hardness of approximation: Gap location
• On approximation algorithms for the minimum satisfiability problem
• Minimizing the weighted sum of squared tardiness on a single machine
• Single machine scheduling to minimize total weighted tardiness
• Approximating MIN 2-SAT and MIN 3-SAT
• Improved approximations for max set splitting and max NAE SAT
• Inapproximability results for set splitting and satisfiability problems with no mixed clauses
• Independent sets with domination constraints
• A case study in programming a quantum annealer for hard operational planning problems
• Worst-case analysis of a new heuristic for the travelling salesman problem
• On the complexity of approximating \(k\)-set packing
• Single Machine Scheduling with Release Dates
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Improved approximation of Max-Cut on graphs of bounded degree
• On the $1.1$ Edge-Coloring of Multigraphs
• The Mathematical Coloring Book
• The importance of being biased
• On Syntactic versus Computational Views of Approximability
• The Minimum Satisfiability Problem
• On the hardness of approximating minimization problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• The Traveling Salesman Problem with Distances One and Two
• Analytical approach to parallel repetition
• Some optimal inapproximability results
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• A Polylogarithmic Approximation of the Minimum Bisection
• On Unapproximable Versions of $NP$-Complete Problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: From the quantum approximate optimization algorithm to a quantum alternating operator ansatz