Verifiable Quantum Advantage via Optimized DQI Circuits

• URL: http://arxiv.org/abs/2510.10967v1
• Date: Mon, 13 Oct 2025 03:19:28 GMT
• Title: Verifiable Quantum Advantage via Optimized DQI Circuits
• Authors: Tanuj Khattar, Noah Shutty, Craig Gidney, Adam Zalcman, Noureldin Yosri, Dmitri Maslov, Ryan Babbush, Stephen P. Jordan,
• Abstract summary: Decoded Quantum Interferometry (DQI) provides a framework for superpolynomial quantum speedups.<n>We apply DQI to the Optimal Polynomial Intersection (OPI) problem, whose code is Reed-Solomon (RS)<n>We establish that DQI for OPI is the first known candidate for verifiable quantum advantage with optimal speedup.
• Score: 2.149968465453488
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Decoded Quantum Interferometry (DQI) provides a framework for superpolynomial quantum speedups by reducing certain optimization problems to reversible decoding tasks. We apply DQI to the Optimal Polynomial Intersection (OPI) problem, whose dual code is Reed-Solomon (RS). We establish that DQI for OPI is the first known candidate for verifiable quantum advantage with optimal asymptotic speedup: solving instances with classical hardness $O(2^N)$ requires only $\widetilde{O}(N)$ quantum gates, matching the theoretical lower bound. Realizing this speedup requires highly efficient reversible RS decoders. We introduce novel quantum circuits for the Extended Euclidean Algorithm, the decoder's bottleneck. Our techniques, including a new representation for implicit B\'ezout coefficient access, and optimized in-place architectures, reduce the leading-order space complexity to the theoretical minimum of $2nb$ qubits while significantly lowering gate counts. These improvements are broadly applicable, including to Shor's algorithm for the discrete logarithm. We analyze OPI over binary extension fields $GF(2^b)$, assess hardness against new classical attacks, and identify resilient instances. Our resource estimates show that classically intractable OPI instances (requiring $>10^{23}$ classical trials) can be solved with approximately 5.72 million Toffoli gates. This is substantially less than the count required for breaking RSA-2048, positioning DQI as a compelling candidate for practical, verifiable quantum advantage.

Related papers

• Fault-tolerant execution of error-corrected quantum algorithms [1.2841574646218608]
  Scaling up quantum algorithms to tackle high-impact problems requires quantum error correction and fault tolerance.<n>We demonstrate the end-to-end execution of logical quantum algorithms using only fault-tolerant (FT) components.<n>Our work demonstrates near-break-even performance of complex, error-corrected quantum circuits using only FT components.
  arXiv  Detail & Related papers  (2026-03-04T20:26:54Z)
• Optimization by Decoded Quantum Interferometry [42.169154389732036]
  We introduce a quantum algorithm called Decoded Quantum Interferometry (DQI)<n>For approximating to data over finite fields, DQI achieves a better approximation ratio than any time known to us.
  arXiv  Detail & Related papers  (2024-08-15T17:47:42Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Quantum Speedup for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection [2.5272389610447856]
  We propose a quantum algorithm that supports a real-valued higher-order unconstrained binary optimization problem. The proposed algorithm is capable of reducing the query complexity in the classical domain and providing a quadratic speedup in the quantum domain.
  arXiv  Detail & Related papers  (2022-05-31T00:14:49Z)
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications [10.436969366019015]
  We show that any $Theta(n)$-depth circuit can be prepared with a $Theta(log(nd)) with $O(ndlog d)$ ancillary qubits. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories.
  arXiv  Detail & Related papers  (2022-01-27T13:16:30Z)
• Deterministic and Entanglement-Efficient Preparation of Amplitude-Encoded Quantum Registers [0.533024001730262]
  A classical vector $mathbfb$ is encoded in the amplitudes of a quantum state. An arbitrary state of $Q$ qubits generally requires approximately $2Q$ entangling gates. We present a deterministic (nonvariational) algorithm that allows one to flexibly reduce the quantum resources required for state preparation.
  arXiv  Detail & Related papers  (2021-10-26T07:37:54Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.