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.

29 pages, 5 figures

References in corpus (7)

• A Quantum Approximate Optimization Algorithm
• 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
• Solving boolean satisfiability problems with the quantum approximate optimization algorithm
• 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