Verifiable quantum advantage: old and new ideas

Verifiable quantum advantage: old and new ideas

by Alexandru Gheorghiu (IBM Quantum)

Formal & Physical Sciences Computing & Cybersecurity UYComputer scienceUYXNatural computing
🎙 Alexandru Gheorghiu (IBM Quantum) 👥 75K 📅 July 16, 2025 ⏱ 64 min 👁 1K 📄 expert opinion 🧭 2026-08-06
Available in: English (current) Français

Keywords

quantum advantageverifiableForrelationinteractive proofsNISQ

Summary

Alexandru Gheorghiu from IBM Quantum presents a talk on verifiable quantum advantage, covering both established approaches and a new idea. He begins by defining verifiable quantum advantage as a task efficiently solvable on a quantum computer, hard classically, and efficiently verifiable classically, ideally implementable on near-term devices. He reviews historical approaches: early algorithms like Shor’s and Simon’s, sampling-based methods like Boson sampling and random circuits, heuristic variational methods, interactive proofs of quantumness, and code-based approaches like Yamakawa-Zhandry and decoded quantum interferometry. He notes that none of these fully satisfy all three criteria of being NISQable, efficiently verifiable, and having in-principle quantum advantage. He then discusses recent progress in quantum factoring, including Gidney’s work on factoring 2048-bit RSA integers with less than a million noisy qubits and a protocol for factoring numbers of the form p^2*q with even smaller circuits. He suggests that elliptic curve discrete log might be broken with even fewer qubits. The main part of the talk introduces a new approach based on the Forrelation problem, defined by Scott Aaronson in 2009. The problem involves determining the correlation between a Boolean function and the Fourier transform of another. A simple quantum circuit can estimate this quantity. The speaker observes that Forrelation has a symmetry property under binary orthogonal transformations. He then outlines how this symmetry can be exploited to construct a verifiable quantum advantage test, though the details are not fully elaborated. The talk concludes with a Q&A session.

241 words

Critical Evaluation

The talk provides a comprehensive overview of the landscape of verifiable quantum advantage, situating the new approach within the field. The speaker is knowledgeable and presents the material with clarity, though the technical depth is high. The review of existing approaches is concise but accurate, highlighting the trade-offs between NISQ implementability, verifiability, and classical hardness. The discussion of recent progress in quantum factoring is particularly valuable, as it suggests that factoring-based approaches might become practical sooner than expected. The new idea based on Forrelation is intriguing, but the presentation is somewhat high-level, with the speaker acknowledging that the details are not yet published. The classical hardness of the proposed task is not fully established, which is a limitation. The speaker is honest about the contributions of his collaborators. The Q&A session adds value, addressing questions about elliptic curve factoring and the choice of the Forrelation problem. Overall, the talk is scientifically rigorous and offers a promising direction for future research, but the lack of a published paper and the incomplete hardness analysis prevent it from receiving a perfect score.

179 words

Title / Content Match

The title accurately reflects the content: the speaker reviews old approaches and then presents a new idea for verifiable quantum advantage.

Quality & Reliability

8/10

Talk by a researcher from IBM Quantum, presenting a novel approach to verifiable quantum advantage based on the Forrelation problem. The talk is technical, references known results, and includes a Q&A session. However, the new approach is not yet published, and the speaker acknowledges that classical hardness is not fully established.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Concurring Sources

Contribution & Novelties

The talk presents a new approach to verifiable quantum advantage based on the Forrelation problem, exploiting its symmetry properties to enable classical verification. This is a novel idea that could potentially bridge the gap between NISQ implementability and verifiability. The speaker also highlights recent progress in quantum factoring that may lead to earlier demonstrations of quantum advantage.

Pour aller plus loin :

94 words

Radar Profile

The radar profile shows high scores in technical level and information quality, reflecting the advanced and detailed nature of the talk. The quantity of information is also high, but the overall reliability is slightly lower due to the unpublished nature of the new approach.

Reliability 8/10