Google Quantum AI researchers have demonstrated a quantum approach to the Optimal Polynomial Intersection (OPI) problem requiring approximately 5.72 million Toffoli gates to solve instances intractable for classical computers, instances demanding over 10^(23) classical trials. Their work establishes Decoded Quantum Interferometry (DQI) for OPI as the first known candidate for verifiable quantum advantage with optimal asymptotic speedup, achieving O(N) quantum gates for problems with O(2^N) classical hardness, matching the theoretical lower bound. The team reduced the leading-order space complexity of their reversible Reed-Solomon decoder circuits to 2nb qubits, a theoretical minimum, and report these improvements are broadly applicable, including to Shor’s algorithm.
DQI and OPI: Verifiable Quantum Advantage Candidate
This efficiency stems from novel quantum circuits developed for the Extended Euclidean Algorithm, a critical bottleneck within the reversible Reed-Solomon (RS) decoder. The circuits reduce the leading-order space complexity to 2nb qubits, matching the theoretical minimum for this task and enabling the claimed quantum advantage.
The work demonstrates a substantial reduction in resource requirements compared to previously explored methods for breaking RSA-2048, positioning Decoded Quantum Interferometry (DQI) as a compelling candidate for practical, verifiable quantum advantage. Researchers estimate that classically intractable OPI instances, those requiring over 10^(23) classical trials, can be solved using approximately 5.72 million Toffoli gates, a concrete figure illustrating the scale of computation now within reach.
This calculation relies on a logical error rate of , achieved using a surface code with 968 physical qubits per logical qubit for hot storage and a 2D Yoked Surface Code with 350 physical qubits per logical qubit for cold storage. Beyond the core algorithmic improvements, the team made code and assets publicly available on Zenodo, facilitating further research and independent verification of their results.
The approach uses Decoded Quantum Interferometry (DQI), a framework for achieving superpolynomial quantum speedups by transforming optimization problems into reversible decoding tasks. Applying DQI to OPI, whose dual code is Reed-Solomon, allows for this optimal scaling, a significant departure from existing verifiable quantum advantage candidates that exceed the theoretical lower bound of N quantum gates.
DQI’s Semicircle Law Guarantees Decoding Performance
The efficiency of quantum decoding algorithms has received a boost from a new analysis of Decoded Quantum Interferometry (DQI), establishing a performance guarantee. Achieving this speedup requires highly efficient reversible RS decoders. Their techniques, including a new representation for implicit Bézout 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.
Extended Euclidean Algorithm for RS Decoding
The Extended Euclidean Algorithm (EEA) forms a critical foundation for efficient quantum Reed-Solomon (RS) decoding, and new circuits targeting this algorithm significantly reduce the number of qubits required for implementation. Researchers have developed highly optimized, reversible quantum circuits for syndrome decoding using EEA-based decoders, addressing a key bottleneck in realizing practical quantum advantage for this class of problem.
These circuits are not limited to decoding; the techniques developed will likely prove useful in other areas of computational number theory, including Elliptic Curve Cryptography. A central innovation lies in shifting analysis from prime fields to binary extension fields, GF(2^b), which allows for significantly cheaper compilation of arithmetic circuits.
By focusing on the EEA, they’ve created a pathway to minimize quantum resource demands, specifically targeting the leading-order space complexity. This optimization is important because the EEA is a cornerstone of both classical and quantum computing, extending beyond its initial application in integer calculations to encompass polynomial domains relevant to RS decoding. This improvement stems from a novel matrix representation of the EEA, enabling more efficient computation of multiplicative inverses in finite fields.
To find the inverse of a polynomial A(z), the EEA is applied to P(z) and A(z), yielding cofactor polynomials u(z) and v(z) such that P(z)u(z) + A(z)v(z) = gcd(P(z),A(z)) = 1. The team believes these improvements are broadly applicable, extending beyond the immediate context of DQI and potentially impacting other quantum algorithms. The analysis of OPI over binary extension fields, GF(2^b), is a key component of this broader applicability, as it simplifies the compilation of arithmetic circuits and reduces the overall resource requirements.
Reversible RS Decoder: Reduced Qubit Space Complexity
Optimized circuits now require only 2*n*b qubits for a reversible Reed-Solomon decoder, matching a long-sought theoretical minimum, according to new work focused on enabling verifiable quantum advantage. By focusing on in-register quotient storage, the researchers deterministically reduced qubit counts to 2*n*b plus a logarithmic correction, O(log n), a critical step toward practical implementation.
This data structure records the execution trace of a constant-time Extended Euclidean Algorithm (EEA), allowing the circuits to use the low gate costs of modern, division-free EEA algorithms without incurring their typical qubit overhead. The work details improvements to classical reversible EEA construction, resulting in lower qubit and gate counts, and formalizes the concept of implicit access to Bézout coefficients.
This allows the team to take advantage of the low gate counts for constant-time division-free variants of the EEA while avoiding high ancilla overhead. “We present an optimized circuit construction that significantly reduces qubit overhead,” the researchers state, highlighting the core achievement of their design. This advance suggests that cold logical qubits will be roughly triple the density of hot logical qubits, an important consideration for scaling quantum computations.
DQI’s O(N) Gate Count Achieves Asymptotic Speedup
This efficiency matches the theoretical lower bound for computation, a milestone detailed in recent work focusing on reversible decoding techniques. The overall circuit size remains O(n^2), but the quantum gate cost for classical runtime is N^(4. 5), a significant reduction in computational demand. This improvement stems from a novel approach to constraint satisfaction problems, where DQI’s efficiency is directly linked to the efficiency of reversible decoding of a related error-correcting code.
The work details a suite of algorithmic and compilation techniques targeting the Extended Euclidean Algorithm (EEA), a critical bottleneck in RS decoding. Combining Theorem IV. 2 and Theorem III. 7, the researchers formally demonstrate Theorem I.1, establishing the asymptotic optimality of their approach. This result surpasses the asymptotic scaling of Shor’s algorithm for cryptography, which requires O(N^6) gates to achieve a comparable speedup in integer factorization.
The team’s findings demonstrate that DQI+OPI is the first known proposal for verifiable superpolynomial speedup that achieves optimal asymptotic efficiency, an important step toward realizing practical quantum advantage. The realization of this speedup relies on the concrete efficiency of the underlying reversible RS decoder. The team’s innovations in algorithmic and compilation techniques represent an advancement in this area.
DQI Application: Improvements to Shor’s Algorithm
This achievement extends beyond the decoder itself, offering broadly applicable improvements to algorithms like Shor’s for the discrete logarithm. Analysis of the Optimal Polynomial Intersection (OPI) problem over binary extension fields GF(2^b) has identified resilient instances and assessed their hardness against new classical attacks. The Extended Euclidean Algorithm, a bottleneck in the decoder’s operation, is now implemented with significantly lowered gate counts. These findings suggest a pathway toward realizing practical quantum algorithms with reduced resource requirements and improved scalability.
👉 More information
🗞 Verifiable quantum advantage via optimized DQI circuits
✍️ Tanuj Khattar, Noah Shutty, Craig Gidney, Adam Zalcman, Noureldin Yosri, Dmitri Maslov, Ryan Babbush and Stephen P. Jordan
🧠 DOI: http://link.aps.org/doi/10.1103/2cxf-9srg




See today’s quantum computing news on Quantum Zeitgeist for the latest breakthroughs in qubits, hardware, algorithms, and industry deals.
