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.

arXiv comment9 pages of main text + 6 figures. Comments are welcome

References in corpus (32)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• A variational eigenvalue solver on a quantum processor
• Quantum Mechanics helps in searching for a needle in a haystack
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Barren plateaus in quantum neural network training landscapes
• The theory of variational hybrid quantum-classical algorithms
• Quantum computational chemistry
• Adiabatic Quantum Computing
• Trapped-Ion Quantum Computing: Progress and Challenges
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Quantum information processing with superconducting circuits: a review
• Quantum algorithms for quantum chemistry and quantum materials science
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum computing with atomic qubits and Rydberg interactions: Progress and challenges
• Quantum optimization using variational algorithms on near-term quantum devices
• Defining and detecting quantum speedup
• Large-scale silicon quantum photonics implementing arbitrary two-qubit processing
• Hybrid quantum-classical algorithms and quantum error mitigation
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Continuous-variable quantum neural networks
• Local random quantum circuits are approximate polynomial-designs
• The Expressive Power of Parameterized Quantum Circuits
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine
• Benchmarking the Quantum Approximate Optimization Algorithm
• Implementation of the XY interaction family with calibration of a single pulse
• Classical Optimizers for Noisy Intermediate-Scale Quantum Devices
• Improved success probability with greater circuit depth for the quantum approximate optimization algorithm
• 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