Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers

Abstract

Quantum annealing (QA) and Quantum Alternating Operator Ansatz (QAOA) are both heuristic quantum algorithms intended for sampling optimal solutions of combinatorial optimization problems. In this article we implement a rigorous direct comparison between QA on D-Wave hardware and QAOA on IBMQ hardware. These two quantum algorithms are also compared against classical simulated annealing. The studied problems are instances of a class of Ising models, with variable assignments of $+1$ or $-1$, that contain cubic $ZZZ$ interactions (higher order terms) and match both the native connectivity of the Pegasus topology D-Wave chips and the heavy hexagonal lattice of the IBMQ chips. The novel QAOA implementation on the heavy hexagonal lattice has a CNOT depth of $6$ per round and allows for usage of an entire heavy hexagonal lattice. Experimentally, QAOA is executed on an ensemble of randomly generated Ising instances with a grid search over $1$ and $2$ round angles using all 127 programmable superconducting transmon qubits of ibm_washington. The error suppression technique digital dynamical decoupling is also tested on all QAOA circuits. QA is executed on the same Ising instances with the programmable superconducting flux qubit devices D-Wave Advantage_system4.1 and Advantage_system6.1 using modified annealing schedules with pauses. We find that QA outperforms QAOA on all problem instances. We also find that dynamical decoupling enables 2-round QAOA to marginally outperform 1-round QAOA, which is not the case without dynamical decoupling.

arXiv commentAccepted at ISC HPC 2023

References in corpus (37)

• Variational Quantum Algorithms
• Quantum Annealing in the Transverse Ising Model
• Dynamical Decoupling of Open Quantum Systems
• Quantum annealing with more than one hundred qubits
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Annealing and Analog Quantum Computation
• Perspectives of quantum annealing: Methods and implementations
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Mathematical Foundation of Quantum Annealing
• Quantum Annealing for Industry Applications: Introduction and Review
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Coherent quantum annealing in a programmable 2000-qubit Ising chain
• Scalable error mitigation for noisy quantum circuits produces competitive expectation values
• Demonstration of fidelity improvement using dynamical decoupling with superconducting qubits
• Demonstration of a scaling advantage for a quantum annealer over simulated annealing
• Entanglement in a quantum annealing processor
• $XY$-mixers: analytical and numerical results for QAOA
• Topological and subsystem codes on low-degree graphs with flag qubits
• Scaling advantage in quantum simulation of geometrically frustrated magnets
• Quantum simulation of a three-body interaction Hamiltonian on an NMR quantum computer
• Mitiq: A software package for error mitigation on noisy quantum computers
• Power of Pausing: Advancing Understanding of Thermalization in Experimental Quantum Annealers
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• Circuit design for multi-body interactions in superconducting quantum annealing system with applications to a scalable architecture
• Robustness of dynamical decoupling sequences
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Multilevel Combinatorial Optimization Across Quantum Architectures
• The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
• Effects of Dynamical Decoupling and Pulse-level Optimizations on IBM Quantum Computers
• Parallel Quantum Annealing
• Scaling Quantum Approximate Optimization on Near-term Hardware
• Sampling on NISQ Devices: "Who's the Fairest One of All?"
• Computational Overhead of Locality Reduction in Binary Optimization Problems
• Multi-round QAOA and advanced mixers on a trapped-ion quantum computer
• Quantum Annealing Algorithms for Boolean Tensor Networks

Cited by in corpus (15)

• 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
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Quantum approximate optimization via learning-based adaptive optimization
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• Provable bounds for noise-free expectation values computed from noisy samples
• Quantum Approximate Multi-Objective Optimization
• 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
• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
• Multi-Objective Optimization and Network Routing with Near-Term Quantum Computers
• Higher-Order Portfolio Optimization with Quantum Approximate Optimization Algorithm
• Determining probability density functions with adiabatic quantum computing
• Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking
• Efficient Online Quantum Circuit Learning with No Upfront Training