Optimization by Decoded Quantum Interferometry

Abstract

Achieving superpolynomial speedups for optimization has long been a central goal for quantum algorithms. Here we introduce Decoded Quantum Interferometry (DQI), a quantum algorithm that uses the quantum Fourier transform to reduce optimization problems to decoding problems. For approximating optimal polynomial fits over finite fields, DQI achieves a superpolynomial speedup over known classical algorithms. The speedup arises because the problem's algebraic structure is reflected in the decoding problem, which can be solved efficiently. We then investigate whether this approach can achieve speedup for optimization problems that lack algebraic structure but have sparse clauses. These problems reduce to decoding LDPC codes, for which powerful decoders are known. To test this, we construct a max-XORSAT instance where DQI finds an approximate optimum significantly faster than general-purpose classical heuristics, such as simulated annealing. While a tailored classical solver can outperform DQI on this instance, our results establish that combining quantum Fourier transforms with powerful decoding primitives provides a promising new path toward quantum speedups for hard optimization problems.

80 pages, 15 figures

References in corpus (7)

• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Probabilistic Analysis of Linear Programming Decoding
• Short-Depth Circuits for Dicke State Preparation
• Efficient Linear Programming Decoding of HDPC Codes
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
• Quantum message-passing algorithm for optimal and efficient decoding
• Quantum State Preparation Using an Exact CNOT Synthesis Formulation

Cited by in corpus (8)

• Efficient preparation of Dicke states
• Quantum computing for genomics: conceptual challenges and practical perspectives
• Quantum Optimization Benchmarking Library - The Intractable Decathlon
• Quantum Circuit Design for Decoded Quantum Interferometry
• Using deep learning to construct stochastic local search SAT solvers with performance bounds
• Quantum Simulation-Based Optimization for Cooling System Design
• Quantum community detection via deterministic elimination
• Decoded Quantum Interferometry Under Noise