Warm-starting quantum optimization

Abstract

There is an increasing interest in quantum algorithms for problems of integer programming and combinatorial optimization. Classical solvers for such problems employ relaxations, which replace binary variables with continuous ones, for instance in the form of higher-dimensional matrix-valued problems (semidefinite programming). Under the Unique Games Conjecture, these relaxations often provide the best performance ratios available classically in polynomial time. Here, we discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of a combinatorial optimization problem and how to analyze properties of the associated quantum algorithms. In particular, this allows the quantum algorithm to inherit the performance guarantees of the classical algorithm. We illustrate this in the context of portfolio optimization, where our results indicate that warm-starting the Quantum Approximate Optimization Algorithm (QAOA) is particularly beneficial at low depth. Likewise, Recursive QAOA for MAXCUT problems shows a systematic increase in the size of the obtained cut for fully connected graphs with random weights, when Goemans-Williamson randomized rounding is utilized in a warm start. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.

References in corpus (9)

• Exploring entanglement and optimization within the Hamiltonian Variational Ansatz
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Quantum Algorithms for Fixed Qubit Architectures
• Pulse-efficient circuit transpilation for quantum applications on cross-resonance-based hardware
• Reinforcement Learning assisted Quantum Optimization
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs
• Analysis of Quantum Approximate Optimization Algorithm under Realistic Noise in Superconducting Qubits
• Krivine diffusions attain the Goemans--Williamson approximation ratio

Cited by in corpus (131)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• Challenges and Opportunities in Quantum Optimization
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Counterdiabaticity and the quantum approximate optimization algorithm
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• Hybrid quantum-classical algorithms for approximate graph coloring
• Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
• Pulse-efficient circuit transpilation for quantum applications on cross-resonance-based hardware
• Efficient encoding of the weighted MAX k-CUT on a quantum computer using QAOA
• QUARK: A Framework for Quantum Computing Application Benchmarking
• Constrained mixers for the quantum approximate optimization algorithm
• Graph neural network initialisation of quantum approximate optimisation
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Challenges of variational quantum optimization with measurement shot noise
• Ancilla-free implementation of generalized measurements for qubits embedded in a qudit space
• Large-scale quantum approximate optimization on non-planar graphs with machine learning noise mitigation
• NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• Scaling Quantum Approximate Optimization on Near-term Hardware
• Lyapunov control-inspired strategies for quantum combinatorial optimization
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
• Pulse variational quantum eigensolver on cross-resonance based hardware
• Quantum Computing Techniques for Multi-Knapsack Problems
• Benchmarking digital quantum simulations above hundreds of qubits using quantum critical dynamics
• Warm-Starting and Quantum Computing: A Systematic Mapping Study
• Architectural Vision for Quantum Computing in the Edge-Cloud Continuum
• Improving the variational quantum eigensolver using variational adiabatic quantum computing
• Approaches to Constrained Quantum Approximate Optimization
• An evolving objective function for improved variational quantum optimisation
• Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem
• Variational quantum algorithm for unconstrained black box binary optimization: Application to feature selection
• Provable bounds for noise-free expectation values computed from noisy samples
• Performance Evaluation and Acceleration of the QTensor Quantum Circuit Simulator on GPUs
• An introduction to variational quantum algorithms for combinatorial optimization problems
• Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement
• Quantum Approximate Multi-Objective Optimization
• Data re-uploading with a single qudit
• Fermionic Quantum Approximate Optimization Algorithm
• Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
• Quantum Local Search with the Quantum Alternating Operator Ansatz
• Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm
• The Quantum Alternating Operator Ansatz for Satisfiability Problems
• Transfer learning of optimal QAOA parameters in combinatorial optimization
• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Mixer-Phaser Ansätze for Quantum Optimization with Hard Constraints
• Quantum Computing and Tensor Networks for Laminate Design: A Novel Approach to Stacking Sequence Retrieval
• Initial State Encoding via Reverse Quantum Annealing and h-gain Features
• A Quantum Computing Approach for the Unit Commitment Problem
• Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters
• Symmetry-informed transferability of optimal parameters in the Quantum Approximate Optimization Algorithm
• Studying the phase diagram of the three-flavor Schwinger model in the presence of a chemical potential with measurement- and gate-based quantum computing
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• A Hybrid Classical Quantum Computing Approach to the Satellite Mission Planning Problem
• Low-depth Clifford circuits approximately solve MaxCut
• Variational Quantum Multi-Objective Optimization
• JuliQAOA: Fast, Flexible QAOA Simulation
• NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization
• Bias-field digitized counterdiabatic quantum optimization
• Bayesian Learning of Parameterised Quantum Circuits
• Enabling High Performance Debugging for Variational Quantum Algorithms using Compressed Sensing
• Approximating under the Influence of Quantum Noise and Compute Power
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT
• QuACS: Variational Quantum Algorithm for Coalition Structure Generation in Induced Subgraph Games
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• Exponential Qubit Reduction in Optimization for Financial Transaction Settlement
• Simulation of a feedback-based algorithm for quantum optimization for a realistic neutral atom system with an optimized small-angle controlled-phase gate
• Efficient DCQO Algorithm within the Impulse Regime for Portfolio Optimization
• Efficient Encodings of the Travelling Salesperson Problem for Variational Quantum Algorithms
• Approaching Collateral Optimization for NISQ and Quantum-Inspired Computing
• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
• Red-QAOA: Efficient Variational Optimization through Circuit Reduction
• Systematic study on the dependence of the warm-start quantum approximate optimization algorithm on approximate solutions
• MLQAOA: Graph Learning Accelerated Hybrid Quantum-Classical Multilevel QAOA
• Quantum Approximate Optimization Algorithm with Sparsified Phase Operator
• Max-cut Clustering Utilizing Warm-Start QAOA and IBM Runtime
• Scalable circuit depth reduction in feedback-based quantum optimization with a quadratic approximation
• Iteration Complexity of Variational Quantum Algorithms
• Detecting quasi-degenerate ground states in topological models via variational quantum eigensolver
• Quantum-classical tradeoffs and multi-controlled quantum gate decompositions in variational algorithms
• Optimized Noise Suppression for Quantum Circuits
• Optimization strategies in WAHTOR algorithm for quantum computing empirical ansatz: a comparative study
• Quantum Relaxation for Solving Multiple Knapsack Problems
• Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
• Inductive Construction of Variational Quantum Circuit for Constrained Combinatorial Optimization
• Hierarchical Multigrid Ansatz for Variational Quantum Algorithms
• LX-mixers for QAOA: Optimal mixers restricted to subspaces and the stabilizer formalism
• QCEDA: Using Quantum Computers for EDA
• Continuous-time quantum optimisation without the adiabatic principle
• Warm Start Adaptive-Bias Quantum Approximate Optimization Algorithm
• Twisted hybrid algorithms for combinatorial optimization
• A Monte Carlo Tree Search approach to QAOA: finding a needle in the haystack
• Universal Resources for QAOA and Quantum Annealing
• Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Noise tailoring for Robust Amplitude Estimation
• Mapping State Transition Susceptibility in Quantum Annealing
• Ising Hamiltonians for Constrained Combinatorial Optimization Problems and the Metropolis-Hastings Warm-Starting Algorithm
• Atom Cavity Encoding for NP-Complete Problems
• Quantum Optimization Benchmarking Library - The Intractable Decathlon
• The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
• A Cutting-plane Method for Semidefinite Programming with Potential Applications on Noisy Quantum Devices
• Constraint-Aware Quantum Optimization via Hamming Weight Operators
• Adiabatic quantum computing with parameterized quantum circuits
• A coherent approach to quantum-classical optimization
• Symmetry-based quantum algorithms for open-shop scheduling with hard constraints
• Warm Start of Variational Quantum Algorithms for Quadratic Unconstrained Binary Optimization Problems
• Efficient Online Quantum Circuit Learning with No Upfront Training
• Digitized Counter-Diabatic Quantum Optimization for Bin Packing Problem
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming
• Approximate Quadratization of High-Order Hamiltonians for Combinatorial Quantum Optimization
• Generative flow-based warm start of the variational quantum eigensolver
• Predict and Conquer: Navigating Algorithm Trade-offs with Quantum Design Automation
• Freedom of mixer rotation-axis improves performance in the quantum approximate optimization algorithm
• Shot-based quantum encoding: a data-loading paradigm for quantum neural networks
• Improving the Quantum Approximate Optimization Algorithm with postselection
• Slice-Wise Initial State Optimization to Improve Cost and Accuracy of the VQE on Lattice Models
• Quantum tree generator improves QAOA state-of-the-art for the knapsack problem
• Pilot-Wave Simulator: Exact Classical Sampling from Ideal and Noisy Quantum Circuits up to Hundreds of Qubits
• Fast collisional $\sqrt{\mathrm{SWAP}}$ gate for fermionic atoms in an optical superlattice
• Qubit-efficient quantum combinatorial optimization solver
• Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers
• Efficient Digital Quadratic Unconstrained Binary Optimization Solvers for SAT Problems
• From Hope to Heuristic: Realistic Runtime Estimates for Quantum Optimisation in NHEP
• The Rise of Quantum Computing -- Take a BITE for Built Environment and Urban Microclimate Research
• Encodings of the weighted MAX k-CUT on qubit systems
• Multiclass Portfolio Optimization via Variational Quantum Eigensolver with Dicke State Ansatz
• A combined quantum-classical method applied to material design: optimization and discovery of photochromic materials for photopharmacology applications