Qubit-efficient encoding schemes for binary optimisation problems

Abstract

We propose and analyze a set of variational quantum algorithms for solving quadratic unconstrained binary optimization problems where a problem consisting of $n_c$ classical variables can be implemented on $\mathcal{O}(\log n_c)$ number of qubits. The underlying encoding scheme allows for a systematic increase in correlations among the classical variables captured by a variational quantum state by progressively increasing the number of qubits involved. We first examine the simplest limit where all correlations are neglected, i.e. when the quantum state can only describe statistically independent classical variables. We apply this minimal encoding to find approximate solutions of a general problem instance comprised of 64 classical variables using 7 qubits. Next, we show how two-body correlations between the classical variables can be incorporated in the variational quantum state and how it can improve the quality of the approximate solutions. We give an example by solving a 42-variable Max-Cut problem using only 8 qubits where we exploit the specific topology of the problem. We analyze whether these cases can be optimized efficiently given the limited resources available in state-of-the-art quantum platforms. Lastly, we present the general framework for extending the expressibility of the probability distribution to any multi-body correlations.

9 pages of main text + 6 figures. Comments are welcome

References in corpus (8)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Quantum algorithms for quantum chemistry and quantum materials science
• Hybrid quantum-classical algorithms and quantum error mitigation
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Classical Optimizers for Noisy Intermediate-Scale Quantum Devices
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets
• Using models to improve optimizers for variational quantum algorithms

Cited by in corpus (16)

• Towards large-scale quantum optimization solvers with few qubits
• Quantum Computing Techniques for Multi-Knapsack Problems
• Towards an Automated Framework for Realizing Quantum Computing Solutions
• NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization
• Qubit-efficient Variational Quantum Algorithms for Image Segmentation
• A Hybrid Quantum-Classical Approach to the Electric Mobility Problem
• Efficient Encodings of the Travelling Salesperson Problem for Variational Quantum Algorithms
• Exponential Qubit Reduction in Optimization for Financial Transaction Settlement
• Probing the limits of variational quantum algorithms for nonlinear ground states on real quantum hardware: The effects of noise
• On the Baltimore Light RailLink into the quantum future
• Deep-Circuit QAOA
• Improving quantum annealing by engineering the coupling to the environment
• Resource-Efficient Hadamard Test Tailored Variational Framework for Nonlinear Dynamics on Quantum Computers
• Efficient Estimation and Sequential Optimization of Cost Functions in Variational Quantum Algorithms
• Graph Coloring via Quantum Optimization on a Rydberg-Qudit Atom Array
• Qubit-efficient quantum combinatorial optimization solver