Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems

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.

48 pages; 11 figures; Accepted to Quantum Journal

References in corpus (14)

• A Quantum Approximate Optimization Algorithm
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Resource-Aware Quantum Programming with General Recursion and Quantum Control
• Liquid State NMR as a Test-bed for Developing Quantum Control Methods
• Pegasus: The second connectivity graph for large-scale quantum annealing hardware
• Quantum approximate optimization algorithm for qudit systems
• Quantum algorithms with local particle number conservation: noise effects and error correction
• Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
• Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms
• Solving Multi-Coloring Combinatorial Optimization Problems Using Hybrid Quantum Algorithms
• An LLVM-based C++ Compiler Toolchain for Variational Hybrid Quantum-Classical Algorithms and Quantum Accelerators
• Quantum approximate algorithm for NP optimization problems with constraints
• 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