Towards large-scale quantum optimization solvers with few qubits

Abstract

We introduce a variational quantum solver for combinatorial optimizations over $m=\mathcal{O}(n^k)$ binary variables using only $n$ qubits, with tunable $k>1$. The number of parameters and circuit depth display mild linear and sublinear scalings in $m$, respectively. Moreover, we analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature. This leads to unprecedented quantum-solver performances. For $m=7000$, numerical simulations produce solutions competitive in quality with state-of-the-art classical solvers. In turn, for $m=2000$, an experiment with $n=17$ trapped-ion qubits featured MaxCut approximation ratios estimated to be beyond the hardness threshold $0.941$. To our knowledge, this is the highest quality attained experimentally on such sizes. Our findings offer a novel heuristics for quantum-inspired solvers as well as a promising route towards solving commercially-relevant problems on near term quantum devices.

References in corpus (35)

• Quantum Computing in the NISQ era and beyond
• Variational Quantum Algorithms
• Barren plateaus in quantum neural network training landscapes
• Noisy intermediate-scale quantum (NISQ) algorithms
• Quantum computational chemistry
• Error mitigation for short-depth quantum circuits
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• Quantum Error Mitigation
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Training variational quantum algorithms is NP-hard
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Local random quantum circuits are approximate polynomial-designs
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps
• Challenges and Opportunities in Quantum Optimization
• Reachability Deficits in Quantum Approximate Optimization
• Equivalence of quantum barren plateaus to cost concentration and narrow gorges
• A Lie Algebraic Theory of Barren Plateaus for Deep Parameterized Quantum Circuits
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Qibo: a framework for quantum simulation with hardware acceleration
• Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
• Parameter Concentration in Quantum Approximate Optimization
• MAXCUT QAOA performance guarantees for p >1
• Random quantum circuits are approximate unitary $t$-designs in depth $O\left(n{t}^{5+o(1)}\right)$
• The Adjoint Is All You Need: Characterizing Barren Plateaus in Quantum Ansätze
• Applying quantum algorithms to constraint satisfaction problems
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage
• Quantum speedup of branch-and-bound algorithms
• Qubit-efficient encoding schemes for binary optimisation problems
• Quantum simulation with just-in-time compilation
• Effects of noise on the overparametrization of quantum neural networks
• NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization
• Exponential Qubit Reduction in Optimization for Financial Transaction Settlement
• Polynomial unconstrained binary optimisation inspired by optical simulation

Cited by in corpus (15)

• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
• Optimized QUBO formulation methods for quantum computing
• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
• Quantum encoder for fixed Hamming-weight subspaces
• Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
• On the Baltimore Light RailLink into the quantum future
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• Optimization via Quantum Preconditioning
• Utility of NISQ devices: optimizing experimental parameters for the fabrication of Au atomic junction using gate-based quantum computers
• Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice
• Quantum Optimization Benchmarking Library - The Intractable Decathlon
• Perspectives on Utilization of Measurements in Quantum Algorithms
• Digitized Counter-Diabatic Quantum Optimization for Bin Packing Problem
• Qubit-efficient quantum combinatorial optimization solver
• Direct Gradient Computation for Barren Plateaus in Parameterized Quantum Circuits