Encoding-Independent Optimization Problem Formulation for Quantum Computing

Abstract

We present an encoding and hardware-independent formulation of optimization problems for quantum computing. Using this generalized approach, we present an extensive library of optimization problems and their various derived spin encodings. Common building blocks that serve as a construction kit for building these spin Hamiltonians are identified. This paves the way towards a fully automatic construction of Hamiltonians for arbitrary discrete optimization problems. The presented freedom in the problem formulation is a key step for tailoring optimal spin Hamiltonians for different hardware platforms.

arXiv comment29 pages, 5 figures

References in corpus (47)

• Quantum Computing in the NISQ era and beyond
• Quantum Simulation
• Ising formulations of many NP problems
• A Quantum Approximate Optimization Algorithm
• Quantum computational chemistry
• Quantum Chemistry in the Age of Quantum Computing
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Computation by Adiabatic Evolution
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer
• $XY$-mixers: analytical and numerical results for QAOA
• Resource-efficient digital quantum simulation of $d$-level systems for photonic, vibrational, and spin-$s$ Hamiltonians
• Scalable global entangling gates on arbitrary ion qubits
• Application of Quantum Annealing to Nurse Scheduling Problem
• Quantum Annealing Implementation of Job-Shop Scheduling
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Quantum Annealing for Constrained Optimization
• On the representation of Boolean and real functions as Hamiltonians for quantum computing
• Domain wall encoding of discrete variables for quantum annealing and QAOA
• A case study of variational quantum algorithms for a job shop scheduling problem
• Improving Hamiltonian encodings with the Gray code
• Circuit design for multi-body interactions in superconducting quantum annealing system with applications to a scalable architecture
• Forecasting financial crashes with quantum computing
• Driver Hamiltonians for constrained optimization in quantum annealing
• Constrained mixers for the quantum approximate optimization algorithm
• Quantum unary approach to option pricing
• Quantum optimization via four-body Rydberg gates
• NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
• Adiabatic Quantum Algorithms for the NP-Complete Maximum-Weight Independent Set, Exact Cover and 3SAT Problems
• Demonstration of tunable three-body interactions between superconducting qubits
• Error correction for encoded quantum annealing
• Parity Quantum Optimization: Compiler
• Controlled-Controlled-Phase Gates for Superconducting Qubits Mediated by a Shared Tunable Coupler
• Understanding domain-wall encoding theoretically and experimentally
• Modular Parity Quantum Approximate Optimization
• Superconducting quantum many-body circuits for quantum simulation and computing
• Solving boolean satisfiability problems with the quantum approximate optimization algorithm
• Multi-round QAOA and advanced mixers on a trapped-ion quantum computer
• Parity Quantum Optimization: Benchmarks
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Minimal Constraints in the Parity Formulation of Optimization Problems
• Parity Quantum Optimization: Encoding Constraints
• Nonpairwise interactions induced by virtual transitions in four coupled artificial atoms
• Evidence that PUBO outperforms QUBO when solving continuous optimization problems with the QAOA
• Low-depth Circuit Implementation of Parity Constraints for Quantum Optimization
• Constant Depth Code Deformations in the Parity Architecture

Cited by in corpus (8)

• Constrained Optimization via Quantum Zeno Dynamics
• Resource analysis of quantum algorithms for coarse-grained protein folding models
• A Hybrid Classical Quantum Computing Approach to the Satellite Mission Planning Problem
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• Reducing the Compilation Time of Quantum Circuits Using Pre-Compilation on the Gate Level
• Boosting quantum annealing performance through direct polynomial unconstrained binary optimization
• Ancillary entangling Floquet kicks for accelerating quantum algorithms
• Resource-Efficient Quantum Optimization via Higher-Order Encoding