High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices

Abstract

The Quantum Alternating Operator Ansatz (QAOA) is a hybrid classical-quantum algorithm that aims to sample the optimal solution(s) of discrete combinatorial optimization problems. We present optimized QAOA circuit constructions for sampling MAX $k$-SAT problems, specifically for $k=3$ and $k=4$. The novel $4$-SAT QAOA circuit construction we present uses measurement based uncomputation, followed by classical feed forward conditional operations. The QAOA circuit parameters for $3$-SAT are optimized via exact classical (noise-free) simulation, using HPC resources to simulate up to $20$ rounds on $10$ qubits. In order to explore the limits of current NISQ devices we execute these optimized QAOA circuits for random $3$-SAT test instances with clause-to-variable ratio $4$ on four trapped ion quantum computers: Quantinuum H1-1 (20 qubits), IonQ Harmony (11 qubits), IonQ Aria 1 (25 qubits), and IonQ Forte (30 qubits). The QAOA circuits that are executed include $n=10$ up to $p=20$, and $n=22$ for $p=1$ and $p=2$. The high round circuits use upwards of 9,000 individual gate instructions, making these some of the largest QAOA circuits executed on NISQ devices. Our main finding is that current NISQ devices perform best at low round counts (i.e., $p=1,\dots ,5$) and then -- as expected due to noise -- gradually start returning satisfiability truth assignments that are no better than randomly picked solutions as the number of QAOA rounds are further increased.

References in corpus (27)

• A Quantum Approximate Optimization Algorithm
• t$|$ket$⟩$ : A Retargetable Compiler for NISQ Devices
• A Race Track Trapped-Ion Quantum Processor
• Resource-Aware Quantum Programming with General Recursion and Quantum Control
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Parameter Concentration in Quantum Approximate Optimization
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers
• Statistical analysis of randomized benchmarking
• QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA
• Quantum Computational Phase Transition in Combinatorial Problems
• Analytical Framework for Quantum Alternating Operator Ansätze
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
• Multi-round QAOA and advanced mixers on a trapped-ion quantum computer
• Solving boolean satisfiability problems with the quantum approximate optimization algorithm
• Simulations of Frustrated Ising Hamiltonians with Quantum Approximate Optimization
• The Quantum Alternating Operator Ansatz for Satisfiability Problems
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• Mixer-Phaser Ansätze for Quantum Optimization with Hard Constraints
• The simplified Toffoli gate implementation by Margolus is optimal
• Multi-programming Cross Platform Benchmarking for Quantum Computing Hardware
• Comparing Quantum Service Offerings

Cited by in corpus (8)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• JuliQAOA: Fast, Flexible QAOA Simulation
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• Mitigating Quantum Gate Errors for Variational Eigensolvers Using Hardware-Inspired Zero-Noise Extrapolation
• Classification and transformations of quantum circuit decompositions for permutation operations