A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
read the original 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}{101 D^{1/2}\, l n\, D}\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 paper has not been read by Pith yet.
Forward citations
Cited by 5 Pith papers
-
Classical State Preparation for Variational Quantum Algorithms via Reinforcement Learning
CRiSP uses neural-guided MCTS and curriculum learning to insert Clifford prefixes before parameterized rotations in VQAs, yielding mean 3.17x and max 45x gains in energy accuracy on 22-qubit QAOA benchmarks versus pri...
-
Beyond Single Trajectories: Optimal Control and Jordan-Lie Algebra in Hybrid Quantum Walks for Combinatorial Optimization
Hybrid quantum walks with optimal dynamical coin operators outperform QAOA on Max-Cut and MIS by accessing a strictly larger Jordan-Lie algebra that enables faster convergence and higher accuracy.
-
Co-Designing Error Mitigation and Error Detection for Logical Qubits
Optimized QED intervals plus steady-state extraction enable PEC+QED to deliver 2-11x lower error than PEC alone on Iceberg codes for QAOA.
-
Improving Feasibility in Quantum Approximate Optimization Algorithm for Vehicle Routing via Constraint-Aware Initialization and Hybrid XY-X Mixing
Constraint-aware initialization and hybrid XY-X mixer in QAOA for VRP yield lower average energies and higher feasible-solution ratios than standard QAOA across ideal, finite-shot, and noisy simulations.
-
Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
Systematic numerical study of QAOA parameter transfer on heavy-hex Ising models with local cubic terms shows transferred angles from small instances yield improving expectation values up to 49 layers on instances up t...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.