Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor

Abstract

We demonstrate the application of the Google Sycamore superconducting qubit quantum processor to combinatorial optimization problems with the quantum approximate optimization algorithm (QAOA). Like past QAOA experiments, we study performance for problems defined on the (planar) connectivity graph of our hardware; however, we also apply the QAOA to the Sherrington-Kirkpatrick model and MaxCut, both high dimensional graph problems for which the QAOA requires significant compilation. Experimental scans of the QAOA energy landscape show good agreement with theory across even the largest instances studied (23 qubits) and we are able to perform variational optimization successfully. For problems defined on our hardware graph we obtain an approximation ratio that is independent of problem size and observe, for the first time, that performance increases with circuit depth. For problems requiring compilation, performance decreases with problem size but still provides an advantage over random guessing for circuits involving several thousand gates. This behavior highlights the challenge of using near-term quantum computers to optimize problems on graphs differing from hardware connectivity. As these graphs are more representative of real world instances, our results advocate for more emphasis on such problems in the developing tradition of using the QAOA as a holistic, device-level benchmark of quantum processors.

19 pages, 15 figures

References in corpus (18)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• Barren plateaus in quantum neural network training landscapes
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Defining and detecting quantum speedup
• Large-scale silicon quantum photonics implementing arbitrary two-qubit processing
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Unsupervised Machine Learning on a Hybrid Quantum Computer
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Benchmarking the Quantum Approximate Optimization Algorithm
• Implementation of the XY interaction family with calibration of a single pulse
• A NASA Perspective on Quantum Computing: Opportunities and Challenges
• Training A Quantum Optimizer
• Improved success probability with greater circuit depth for the quantum approximate optimization algorithm
• Using models to improve optimizers for variational quantum algorithms

Cited by in corpus (263)

• Noisy intermediate-scale quantum (NISQ) algorithms
• Strong quantum computational advantage using a superconducting quantum processor
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• Demonstration of multi-qubit entanglement and algorithms on a programmable neutral atom quantum computer
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• A Race Track Trapped-Ion Quantum Processor
• General parameter-shift rules for quantum gradients
• Warm-starting quantum optimization
• Realization of high-fidelity CZ and ZZ-free iSWAP gates with a tunable coupler
• Fermionic partial tomography via classical shadows
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Exponential Error Suppression for Near-Term Quantum Devices
• Quantum Algorithm Implementations for Beginners
• Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond
• Avoiding barren plateaus using classical shadows
• Filtering variational quantum algorithms for combinatorial optimization
• Noisy intermediate-scale quantum computers
• Digitized-counterdiabatic quantum approximate optimization algorithm
• Parameter Concentration in Quantum Approximate Optimization
• MAXCUT QAOA performance guarantees for p >1
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• Observing ground-state properties of the Fermi-Hubbard model using a scalable algorithm on a quantum computer
• Many-body physics in the NISQ era: quantum programming a discrete time crystal
• Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Neural Predictor based Quantum Architecture Search
• Quantum Computing for Molecular Biology
• Biology and medicine in the landscape of quantum advantages
• Pulse-efficient circuit transpilation for quantum applications on cross-resonance-based hardware
• A case study of variational quantum algorithms for a job shop scheduling problem
• Classical variational simulation of the Quantum Approximate Optimization Algorithm
• NISQ Computers: A Path to Quantum Supremacy
• On the practical usefulness of the Hardware Efficient Ansatz
• Digitized-Counterdiabatic Quantum Algorithm for Protein Folding
• A density-matrix renormalization group algorithm for simulating quantum circuits with a finite fidelity
• Fast logic with slow qubits: microwave-activated controlled-Z gate on low-frequency fluxoniums
• Using models to improve optimizers for variational quantum algorithms
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Benchmarking quantum computers
• Solving Graph Problems Using Gaussian Boson Sampling
• Quantum Algorithms for Mixed Binary Optimization applied to Transaction Settlement
• Characterizing local noise in QAOA circuits
• Analyzing the Performance of Variational Quantum Factoring on a Superconducting Quantum Processor
• Effects of Dynamical Decoupling and Pulse-level Optimizations on IBM Quantum Computers
• Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers
• Variational quantum eigensolver for the Heisenberg antiferromagnet on the kagome lattice
• Optimizing quantum gates towards the scale of logical qubits
• Quantum variational optimization: The role of entanglement and problem hardness
• Graph neural network initialisation of quantum approximate optimisation
• Demonstration of quantum volume 64 on a superconducting quantum computing system
• Benchmarking quantum co-processors in an application-centric, hardware-agnostic and scalable way
• Error propagation in NISQ devices for solving classical optimization problems
• Training Saturation in Layerwise Quantum Approximate Optimisation
• Robust resource-efficient quantum variational ansatz through evolutionary algorithm
• Approaching the theoretical limit in quantum gate decomposition
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
• Progress toward favorable landscapes in quantum combinatorial optimization
• Quantum approximate optimization via learning-based adaptive optimization
• Qubit-efficient encoding schemes for binary optimisation problems
• To quantum or not to quantum: towards algorithm selection in near-term quantum optimization
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs
• Challenges of variational quantum optimization with measurement shot noise
• Application-Motivated, Holistic Benchmarking of a Full Quantum Computing Stack
• Variational Hamiltonian simulation for translational invariant systems via classical pre-processing
• Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems
• Practical distributed quantum information processing with LOCCNet
• Compiling Quantum Circuits for Dynamically Field-Programmable Neutral Atoms Array Processors
• Modeling and mitigation of cross-talk effects in readout noise with applications to the Quantum Approximate Optimization Algorithm
• Large-scale quantum approximate optimization on non-planar graphs with machine learning noise mitigation
• Symmetry enhanced variational quantum spin eigensolver
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• Exploiting Symmetry Reduces the Cost of Training QAOA
• Comparative study of variations in quantum approximate optimization algorithms for the Traveling Salesman Problem
• Evaluation of QAOA based on the approximation ratio of individual samples
• Scaling Quantum Approximate Optimization on Near-term Hardware
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• Active Readout Error Mitigation
• An entanglement perspective on the quantum approximate optimization algorithm
• Lyapunov control-inspired strategies for quantum combinatorial optimization
• Quantum Approximate Optimization Algorithm with Adaptive Bias Fields
• Optimal Qubit Mapping with Simultaneous Gate Absorption
• Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices
• A semi-agnostic ansatz with variable structure for quantum machine learning
• Vacuum-gap transmon qubits realized using flip-chip technology
• Quantum Information Scrambling: From Holography to Quantum Simulators
• Quantum algorithms with local particle number conservation: noise effects and error correction
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
• Pulse variational quantum eigensolver on cross-resonance based hardware
• A Variational Quantum Attack for AES-like Symmetric Cryptography
• Stochastic Gradient Line Bayesian Optimization for Efficient Noise-Robust Optimization of Parameterized Quantum Circuits
• Predicting quantum dynamical cost landscapes with deep learning
• Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems
• Variational quantum algorithm with information sharing
• Quantum Computational Phase Transition in Combinatorial Problems
• Few-photon all-optical phase rotation in a quantum-well micropillar cavity
• Quantum Approximate Optimization Algorithm pseudo-Boltzmann states
• Variational waveguide QED simulators
• Hamiltonian operator approximation for energy measurement and ground state preparation
• Applying quantum approximate optimization to the heterogeneous vehicle routing problem
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
• Controlled-Controlled-Phase Gates for Superconducting Qubits Mediated by a Shared Tunable Coupler
• Training variational quantum circuits with CoVaR: covariance root finding with classical shadows
• Optimal Control for Closed and Open System Quantum Optimization
• Analytical Framework for Quantum Alternating Operator Ansätze
• Designing calibration and expressivity-efficient instruction sets for quantum computing
• Reachability Deficits in Quantum Approximate Optimization of Graph Problems
• Microwave-multiplexed qubit controller using adiabatic superconductor logic
• Fragmented imaginary-time evolution for early-stage quantum signal processors
• HAMMER: boosting fidelity of noisy Quantum circuits by exploiting Hamming behavior of erroneous outcomes
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
• Modular Parity Quantum Approximate Optimization
• Efficient estimation of trainability for variational quantum circuits
• Limitations of optimization algorithms on noisy quantum devices
• Calibrating the role of entanglement in variational quantum circuits
• Group-theoretic error mitigation enabled by classical shadows and symmetries
• Shortcuts to Quantum Approximate Optimization Algorithm
• Compact quantum kernel-based binary classifier
• Quantum Dropout: On and Over the Hardness of Quantum Approximate Optimization Algorithm
• Extending relax-and-round combinatorial optimization solvers with quantum correlations
• Superconducting quantum many-body circuits for quantum simulation and computing
• Greedy parameter optimization for diabatic quantum annealing
• A SAT approach to the initial mapping problem in SWAP gate insertion for commuting gates
• Multi-Angle QAOA Does Not Always Need All Its Angles
• Multi-round QAOA and advanced mixers on a trapped-ion quantum computer
• Networked Quantum Services
• Solving optimization problems with local light shift encoding on Rydberg quantum annealers
• Optimizing Counterdiabaticity by Variational Quantum Circuits
• Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm
• Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
• Parity Quantum Optimization: Benchmarks
• Transfer learning of optimal QAOA parameters in combinatorial optimization
• Optimal joint cutting of two-qubit rotation gates
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
• Mixer-Phaser Ansätze for Quantum Optimization with Hard Constraints
• Quantum gradient descent algorithms for nonequilibrium steady states and linear algebraic systems
• Leveraging Randomized Compiling for the QITE Algorithm
• Cryogenic Multiplexing Control Chip for Superconducting Quantum Processor
• A stabilizer framework for Contextual Subspace VQE and the noncontextual projection ansatz
• Pauli path simulations of noisy quantum circuits beyond average case
• Testing Scalable Bell Inequalities for Quantum Graph States on IBM Quantum Devices
• Fast, high precision dynamics in quantum optimal control theory
• Continuous-variable quantum approximate optimization on a programmable photonic quantum processor
• Detecting Violations of Differential Privacy for Quantum Algorithms
• Dynamic-ADAPT-QAOA: An algorithm with shallow and noise-resilient circuits
• Computationally Efficient Quantum Expectation with Extended Bell Measurements
• Fair Sampling Error Analysis on NISQ Devices
• Improving Performance in Combinatorial Optimization Problems with Inequality Constraints: An Evaluation of the Unbalanced Penalization Method on D-Wave Advantage
• Optimizing Quantum Algorithms on Bipotent Architectures
• Binary Control Pulse Optimization for Quantum Systems
• Quantum adiabatic optimization with Rydberg arrays: localization phenomena and encoding strategies
• Highly optimized quantum circuits synthesized via data-flow engines
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Automatic Depth Optimization for Quantum Approximate Optimization Algorithm
• Single-component gradient rules for variational quantum algorithms
• Algorithm-Oriented Qubit Mapping for Variational Quantum Algorithms
• QAOA with $N\cdot p\ge 200$
• Robustness of Variational Quantum Algorithms against stochastic parameter perturbation
• Next nearest neighbour coupling with spinor polariton condensates
• Protocols for classically training quantum generative models on probability distributions
• Enabling High Performance Debugging for Variational Quantum Algorithms using Compressed Sensing
• Certificates of quantum many-body properties assisted by machine learning
• Progress towards analytically optimal angles in quantum approximate optimisation
• Calibration-Aware Transpilation for Variational Quantum Optimization
• NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization
• Individual-Ion Addressing and Readout in a Penning Trap
• Performance of Quantum Approximate Optimization with Quantum Error Detection
• Synergistic Dynamical Decoupling and Circuit Design for Enhanced Algorithm Performance on Near-Term Quantum Devices
• Evaluating the Resilience of Variational Quantum Algorithms to Leakage Noise
• Improving the performance of quantum approximate optimization for preparing non-trivial quantum states without translational symmetry
• Digital quantum simulation of non-perturbative dynamics of open systems with orthogonal polynomials
• Operational Quantum Average-Case Distances
• Exploring Quantum Average-Case Distances: proofs, properties, and examples
• Variational generation of spin squeezing on one-dimensional quantum devices with nearest-neighbor interactions
• Solving combinatorial optimization problems through stochastic Landau-Lifshitz-Gilbert dynamical systems
• Optimal control of a quantum sensor: A fast algorithm based on an analytic solution
• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
• Highly Efficient Encoding for Job-Shop Scheduling Problems and its Application on Quantum Computers
• Hybrid quantum-classical unsupervised data clustering based on the self-organizing feature map
• Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits
• Characterization and tomography of a hidden qubit
• Parameter-Parallel Distributed Variational Quantum Algorithm
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• Efficient DCQO Algorithm within the Impulse Regime for Portfolio Optimization
• Exponential Qubit Reduction in Optimization for Financial Transaction Settlement
• Generating Target Graph Couplings for QAOA from Native Quantum Hardware Couplings
• Improving the Performance of Digitized Counterdiabatic Quantum Optimization via Algorithm-Oriented Qubit Mapping
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• Rapid quantum approaches for combinatorial optimisation inspired by optimal state-transfer
• Simulation of a feedback-based algorithm for quantum optimization for a realistic neutral atom system with an optimized small-angle controlled-phase gate
• Quantum approximate optimization algorithm with random and subgraph phase operators
• Decomposition Pipeline for Large-Scale Portfolio Optimization with Applications to Near-Term Quantum Computing
• Modelling noise in global Molmer-Sorensen interactions applied to quantum approximate optimization
• Variational quantum simulation of long-range interacting systems
• Quantum Approximate Optimization Algorithm with Sparsified Phase Operator
• Realizing a Continuous Set of Two-Qubit Gates Parameterized by an Idle Time
• Quantum Natural Gradient optimizer on noisy platforms: QAOA as a case study
• Mitigating Quantum Gate Errors for Variational Eigensolvers Using Hardware-Inspired Zero-Noise Extrapolation
• Robust Finite-Temperature Many-Body Scarring on a Quantum Computer
• Connection between single-layer Quantum Approximate Optimization Algorithm interferometry and thermal distributions sampling
• A framework for optimal quantum spatial search using alternating phase-walks
• Optical Direct Write of Dolan--Niemeyer-Bridge Junctions for Transmon Qubits
• Optimized Noise Suppression for Quantum Circuits
• Compact inductor-capacitor resonators at sub-gigahertz frequencies
• Efficient Frequency Allocation for Superconducting Quantum Processors Using Improved Optimization Techniques
• High-precision tomography of ion qubits based on registration of fluorescent photons
• Warm Start Adaptive-Bias Quantum Approximate Optimization Algorithm
• Quantum annealing of Cayley-tree Ising spins at small scales
• Hidden variable model for quantum computation with magic states on qudits of any dimension
• Pitfalls of the sublinear QAOA-based factorization algorithm
• Comparing planar quantum computing platforms at the quantum speed limit
• Scalable Parity Architecture With a Shuttling-Based Spin Qubit Processor
• QCEDA: Using Quantum Computers for EDA
• SWAP-less Implementation of Quantum Algorithms
• Verification of a resetting protocol for an uncontrolled superconducting qubit
• Optimization via Quantum Preconditioning
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Tabu-driven Quantum Neighborhood Samplers
• Quantum Scar States in Coupled Random Graph Models
• Depth scaling of unstructured search via quantum approximate optimization
• Hyperoptimized approximate contraction of tensor networks for rugged-energy-landscape spin glasses on periodic square and cubic lattices
• Full Characterization of the Depth Overhead for Quantum Circuit Compilation with Arbitrary Qubit Connectivity Constraint
• Deep-Circuit QAOA
• MLQM: Machine Learning Approach for Accelerating Optimal Qubit Mapping
• Constraint-Aware Quantum Optimization via Hamming Weight Operators
• Minimizing readout-induced noise for early fault-tolerant quantum computers
• Optimal solutions to quantum annealing using two independent control functions
• End-to-End Protocol for High-Quality QAOA Parameters with Few Shots
• Krylov Spread Complexity of Quantum-Walks
• Comparing Quantum Service Offerings
• Error Analysis of the Variational Quantum Eigensolver Algorithm
• Validity condition for high-fidelity Digitized Quantum Annealing
• Batched Line Search Strategy for Navigating through Barren Plateaus in Quantum Circuit Training
• Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem
• It's Quick to be Square: Fast Quadratisation for Quantum Toolchains
• Qubit Readout Error Mitigation with Bit-flip Averaging
• Sub-universal variational circuits for combinatorial optimization problems
• Digital Zero-Noise Extrapolation with Quantum Circuit Unoptimization
• Experimental factoring integers using fixed-point-QAOA with a trapped-ion quantum processor
• Quantum correlation generation capability of experimental processes
• Approximate Quadratization of High-Order Hamiltonians for Combinatorial Quantum Optimization
• Computational Phase Transitions: Benchmarking Ising Machines and Quantum Optimisers
• Signatures of quantum chaos and complexity in the Ising model on random graphs
• Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming
• Symmetry-based quantum algorithms for open-shop scheduling with hard constraints
• Universal Euler-Cartan Circuits for Quantum Field Theories
• Evidence for effectively constant shot complexity in the quantum approximate optimization algorithm without per-instance optimization
• Dynamic LOCC Circuits for Automated Entanglement Manipulation
• Exploiting biased noise in variational quantum models
• Applying Grover-mixer quantum alternating operator ansatz algorithm to higher-order unconstrained binary optimization problems
• Proposal for an autonomous quantum heat engine
• Improving the trainability of VQE on NISQ computers for solving portfolio optimization using convex interpolation
• Quantum Alternating Operator Ansatz for the Preparation and Detection of Long-Lived Singlet States in NMR
• Matrix Product State on a Quantum Computer
• Sampling (noisy) quantum circuits through randomized rounding
• Exploring Entanglement and Parameter Sensitivity in QAOA through Quantum Fisher Information
• Simulating collider physics on quantum computers using effective field theories
• Qubit-efficient quantum combinatorial optimization solver