Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
arXiv:2203.14432 · doi:10.22331/q-2023-09-14-1111
Abstract
Challenging combinatorial optimization problems are ubiquitous in science and engineering. Several quantum methods for optimization have recently been developed, in different settings including both exact and approximate solvers. Addressing this field of research, this manuscript has three distinct purposes. First, we present an intuitive method for synthesizing and analyzing discrete (i.e., integer-based) optimization problems, wherein the problem and corresponding algorithmic primitives are expressed using a discrete quantum intermediate representation (DQIR) that is encoding-independent. This compact representation often allows for more efficient problem compilation, automated analyses of different encoding choices, easier interpretability, more complex runtime procedures, and richer programmability, as compared to previous approaches, which we demonstrate with a number of examples. Second, we perform numerical studies comparing several qubit encodings; the results exhibit a number of preliminary trends that help guide the choice of encoding for a particular set of hardware and a particular problem and algorithm. Our study includes problems related to graph coloring, the traveling salesperson problem, factory/machine scheduling, financial portfolio rebalancing, and integer linear programming. Third, we design low-depth graph-derived partial mixers (GDPMs) up to 16-level quantum variables, demonstrating that compact (binary) encodings are more amenable to QAOA than previously understood. We expect this toolkit of programming abstractions and low-level building blocks to aid in designing quantum algorithms for discrete combinatorial problems.
arXiv comment48 pages; 11 figures; Accepted to Quantum Journal
References in corpus (90)
- SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
- Elementary gates for quantum computation
- Variational Quantum Algorithms
- Ising formulations of many NP problems
- Barren plateaus in quantum neural network training landscapes
- The theory of variational hybrid quantum-classical algorithms
- A Quantum Approximate Optimization Algorithm
- Adiabatic Quantum Computing
- Hamiltonian Simulation by Qubitization
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Simulating Hamiltonian dynamics with a truncated Taylor series
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
- Quantum optimization using variational algorithms on near-term quantum devices
- Variational ansatz-based quantum simulation of imaginary time evolution
- Perspectives of quantum annealing: Methods and implementations
- A Theory of Trotter Error
- Training variational quantum algorithms is NP-hard
- Hamiltonian simulation with nearly optimal dependence on all parameters
- A random compiler for fast Hamiltonian simulation
- Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
- Resource-Aware Quantum Programming with General Recursion and Quantum Control
- Synthesis and Optimization of Reversible Circuits - A Survey
- Experimental signature of programmable quantum annealing
- Obstacles to State Preparation and Variational Optimization from Symmetry Protection
- Blueprint for a microwave trapped-ion quantum computer
- Warm-starting quantum optimization
- Measurement Optimization in the Variational Quantum Eigensolver Using a Minimum Clique Cover
- Efficient Symmetry-Preserving State Preparation Circuits for the Variational Quantum Eigensolver Algorithm
- Reverse Quantum Annealing Approach to Portfolio Optimization Problems
- Adiabatic Quantum Computation in Open Systems
- Scalable quantum circuit and control for a superconducting surface code
- -mixers: analytical and numerical results for QAOA
- Faster quantum simulation by randomization
- Resource-efficient digital quantum simulation of -level systems for photonic, vibrational, and spin- Hamiltonians
- Liquid State NMR as a Test-bed for Developing Quantum Control Methods
- Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management
- Electron-Phonon Systems on a Universal Quantum Computer
- Quantum Annealing Implementation of Job-Shop Scheduling
- Optimal Protocols in Quantum Annealing and QAOA Problems
- Thermally assisted adiabatic quantum computation
- Parameter Concentration in Quantum Approximate Optimization
- Counterdiabaticity and the quantum approximate optimization algorithm
- Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
- Digital quantum simulation of molecular vibrations
- Quantum Annealing for Constrained Optimization
- Hardware Efficient Quantum Algorithms for Vibrational Structure Calculations
- On the representation of Boolean and real functions as Hamiltonians for quantum computing
- Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
- Domain wall encoding of discrete variables for quantum annealing and QAOA
- A case study of variational quantum algorithms for a job shop scheduling problem
- How many qubits are needed for quantum computational supremacy?
- Unconstrained Binary Models of the Travelling Salesman Problem Variants for Quantum Optimization
- Pegasus: The second connectivity graph for large-scale quantum annealing hardware
- Feedback-based quantum optimization
- Error mitigation for variational quantum algorithms through mid-circuit measurements
- Driver Hamiltonians for constrained optimization in quantum annealing
- Efficient encoding of the weighted MAX k-CUT on a quantum computer using QAOA
- Constrained mixers for the quantum approximate optimization algorithm
- Near- and long-term quantum algorithmic approaches for vibrational spectroscopy
- Quantum unary approach to option pricing
- Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding
- Scaling overhead of embedding optimization problems in quantum annealing
- Quantum approximate optimization algorithm for qudit systems
- QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA
- Quantum algorithms with local particle number conservation: noise effects and error correction
- Quantum Algorithms for Scientific Computing and Approximate Optimization
- Quantum Computer-Aided design of Quantum Optics Hardware
- Open system quantum annealing in mean field models with exponential degeneracy
- Two quantum Ising algorithms for the Shortest Vector Problem: one for now and one for later
- Understanding domain-wall encoding theoretically and experimentally
- Bounds on approximating Max XOR with quantum and classical local algorithms
- Dilution effects in spin 7/2 systems. The case of the antiferromagnet GdRhIn
- Reachability Deficits in Quantum Approximate Optimization of Graph Problems
- Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
- Numerical Gate Synthesis for Quantum Heuristics on Bosonic Quantum Processors
- Ferromagnetically shifting the power of pausing
- Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms
- Solving Multi-Coloring Combinatorial Optimization Problems Using Hybrid Quantum Algorithms
- Quantum-accelerated constraint programming
- Classical algorithms and quantum limitations for maximum cut on high-girth graphs
- An LLVM-based C++ Compiler Toolchain for Variational Hybrid Quantum-Classical Algorithms and Quantum Accelerators
- Quantum computing approach to railway dispatching and conflict management optimization on single-track railway lines
- Quantum approximate algorithm for NP optimization problems with constraints
- Divide and Conquer for Combinatorial Optimization and Distributed Quantum Computation
- Graph Optimization Perspective for Low-Depth Trotter-Suzuki Decomposition
- On connectivity-dependent resource requirements for digital quantum simulation of -level particles
- Quantum Integer Programming (QuIP) 47-779: Lecture Notes
- mat2qubit: A lightweight pythonic package for qubit encodings of vibrational, bosonic, graph coloring, routing, scheduling, and general matrix problems
Cited by in corpus (8)
- Challenges and Opportunities in Quantum Optimization
- Encoding-Independent Optimization Problem Formulation for Quantum Computing
- Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
- Resource analysis of quantum algorithms for coarse-grained protein folding models
- Variational Quantum Multi-Objective Optimization
- Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs
- IF-QAOA: A Penalty-Free Approach to Accelerating Constrained Quantum Optimization
- Variational simulation of higher-spin systems on qubit-based quantum simulators