A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem

Abstract

We apply our recent Quantum Approximate Optimization Algorithm to the combinatorial problem of bounded occurrence Max E3LIN2. The input is a set of linear equations each of which contains exactly three boolean variables and each equation says that the sum of the variables mod 2 is 0 or is 1. Every variable is in no more than D equations. A random string will satisfy 1/2 of the equations. We show that the level one QAOA will efficiently produce a string that satisfies $\left(\frac{1}{2}+\frac{1}{101D^{1/2}lnD}\right)$ times the number of equations. A recent classical algorithm achieved $\left(\frac{1}{2}+\frac{constant}{D^{1/2}}\right)$. We also show that in the typical case the quantum computer will output a string that satisfies $\left(\frac{1}{2}+\frac{1}{2\sqrt{3e}{D}^{1/2}}\right)$ times the number of equations.

This version contains a tighter analysis that leads to stronger results on the performance of the quantum algorithm

Cited by in corpus (72)

• Quantum algorithms: an overview
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Large-scale silicon quantum photonics implementing arbitrary two-qubit processing
• Quantum machine learning: a classical perspective
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• The Future of Quantum Computing with Superconducting Qubits
• Warm-starting quantum optimization
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Compiling quantum circuits to realistic hardware architectures using temporal planners
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• Variational Quantum Boltzmann Machines
• Quantum Algorithms for Fixed Qubit Architectures
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Pulse-efficient circuit transpilation for quantum applications on cross-resonance-based hardware
• Training A Quantum Optimizer
• Quantum approximate optimization is computationally universal
• Fast quantum circuit cutting with randomized measurements
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Simulation of Qubit Quantum Circuits via Pauli Propagation
• Error mitigation for variational quantum algorithms through mid-circuit measurements
• Network Community Detection On Small Quantum Computers
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• Training Optimization for Gate-Model Quantum Neural Networks
• qTorch: The Quantum Tensor Contraction Handler
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs
• NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
• Evaluation of QAOA based on the approximation ratio of individual samples
• Learning Unitaries by Gradient Descent
• Comparison of QAOA with Quantum and Simulated Annealing
• Quantum State Optimization and Computational Pathway Evaluation for Gate-Model Quantum Computers
• Development of an Undergraduate Quantum Engineering Degree
• Analytical Framework for Quantum Alternating Operator Ansätze
• Performance of QAOA on Typical Instances of Constraint Satisfaction Problems with Bounded Degree
• Threshold-Based Quantum Optimization
• Extremal eigenvalues of local Hamiltonians
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• What do QAOA energies reveal about graphs?
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• QED driven QAOA for network-flow optimization
• Variational quantum solutions to the Shortest Vector Problem
• Fair Sampling Error Analysis on NISQ Devices
• Complexity of Supersymmetric Systems and the Cohomology Problem
• Automatic Depth Optimization for Quantum Approximate Optimization Algorithm
• Robust optimization for quantum reinforcement learning control using partial observations
• From Ansätze to Z-gates: a NASA View of Quantum Computing
• Trainability Barriers in Low-Depth QAOA Landscapes
• Small quantum computers and large classical data sets
• JuliQAOA: Fast, Flexible QAOA Simulation
• Forbidden subspaces for level-1 QAOA and IQP circuits
• A quantum algorithm to count weighted ground states of classical spin Hamiltonians
• Hierarchical Multigrid Ansatz for Variational Quantum Algorithms
• The 7 faces of quantum NP
• An explicit vector algorithm for high-girth MaxCut
• Syndrome decoding by quantum approximate optimization
• Lower Bounds on Circuit Depth of the Quantum Approximate Optimization Algorithm
• Energy levels estimation on a quantum computer by evolution of a physical quantity
• Applying the Quantum Alternating Operator Ansatz to the Graph Matching Problem
• Improving the Quantum Approximate Optimization Algorithm with postselection
• Maritime Just-in-time navigation with Quantum algorithms
• An Analysis of the Quantum Approximation Optimisation Algorithm
• Resilience-Runtime Tradeoff Relations for Quantum Algorithms