An official website of the United States government
Achieving quantum computational advantage requires solving a classically intractable problem on a quantum device. Natural proposals rely upon the intrinsic hardness of classically simulating quantum mechanics; however, verifying the output is itself classically intractable. On the other hand, certain quantum algorithms (e.g. prime factorization via Shor's algorithm) are efficiently verifiable, but require more resources than what is available on near-term devices. One way to bridge the gap between verifiability and implementation is to use "interactions" between a prover and a verifier. By leveraging cryptographic functions, such protocols enable the classical verifier to enforce consistency in a quantum prover's responses across multiple rounds of interaction. In this work, we demonstrate the first implementation of an interactive quantum advantage protocol, using an ion trap quantum computer. We execute two complementary protocols -- one based upon the learning with errors problem and another where the cryptographic construction implements a computational Bell test. To perform multiple rounds of interaction, we implement mid-circuit measurements on a subset of trapped ion qubits, with subsequent coherent evolution. For both protocols, the performance exceeds the asymptotic bound for classical behavior; maintaining this fidelity at scale would conclusively demonstrate verifiable quantum advantage.
more »
« less
This content will become publicly available on March 31, 2027
A Cryptographic Perspective on the Verifiability of Quantum Advantage
In recent years, achieving verifiable quantum advantage on a NISQ device has emerged as an important open problem in quantum information. The sampling-based quantum advantages are not known to have efficient verification methods. This article investigates the verification of quantum advantage from a cryptographic perspective. We establish a strong connection between the verifiability of quantum advantage and cryptographic and complexity primitives, including efficiently samplable, statistically far but computationally indistinguishable pairs of (mixed) quantum states (EFI), pseudorandom states (PRS), and variants of minimum circuit size problems (MCSP). Specifically, we prove that a) a sampling-based quantum advantage is either verifiable or can be used to buildEFIand evenPRSand b) polynomial-time algorithms for a variant ofMCSPwould imply efficient verification of quantum advantages. Our work shows that the quest for verifiable quantum advantages may lead to applications of quantum cryptography, and the construction of quantum primitives can provide new insights into the verifiability of quantum advantages.
more »
« less
- Award ID(s):
- 2243659
- PAR ID:
- 10656686
- Publisher / Repository:
- ACM
- Date Published:
- Journal Name:
- ACM Transactions on Quantum Computing
- Volume:
- 7
- Issue:
- 1
- ISSN:
- 2643-6809
- Page Range / eLocation ID:
- 1 to 20
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Aref, Walid G. (Ed.)The proliferation of mobile phones and location-based services has given rise to an explosive growth in spatial data. In order to enable spatial data analytics, spatial data needs to be streamed into a data stream warehouse system that can provide real-time analytical results over the most recent and historical spatial data in the warehouse. Existing data stream warehouse systems are not tailored for spatial data. In this paper, we introduce theSTARsystem.STARis a distributed in-memory data stream warehouse system that provides low-latency and up-to-date analytical results over a fast-arriving spatial data stream.STARsupports both snapshot and continuous queries that are composed of aggregate functions and ad hoc query constraints over spatial, textual, and temporal data attributes.STARimplements a cache-based mechanism to facilitate the processing of snapshot queries that collectively utilizes the techniques of query-based caching (i.e., view materialization) and object-based caching. Moreover, to speed-up processing continuous queries,STARproposes a novel index structure that achieves high efficiency in both object checking and result updating. Extensive experiments over real data sets demonstrate the superior performance ofSTARover existing systems.more » « less
-
Infectious diseases, like COVID-19, pose serious challenges to university campuses, which typically adopt closure as a non-pharmaceutical intervention to control spread and ensure a gradual return to normalcy. Intervention policies, such as remote instruction (RI) where large classes are offered online, reduce potential contact but also have broad side-effects on campus by hampering the local economy, students’ learning outcomes, and community wellbeing. In this paper, we demonstrate that university policymakers can mitigate these tradeoffs by leveraging anonymized data from their WiFi infrastructure to learn community mobility—a methodology we refer to asWiFi mobility models(WiMob). This approach enables policymakers to explore more granular policies like localized closures (LC).WiMobcan construct contact networks that capture behavior in various spaces, highlighting new potential transmission pathways and temporal variation in contact behavior. Additionally,WiMobenables us to designLCpolicies that close super-spreader locations on campus. By simulating disease spread with contact networks fromWiMob, we find thatLCmaintains the same reduction in cumulative infections asRIwhile showing greater reduction in peak infections and internal transmission. Moreover,LCreduces campus burden by closing fewer locations, forcing fewer students into completely online schedules, and requiring no additional isolation.WiMobcan empower universities to conceive and assess a variety of closure policies to prevent future outbreaks.more » « less
-
A proof system is publicly verifiable, if anyone, by looking at the transcript of the proof, can be convinced that the corresponding theorem is true. Public verifiability is important in many applications since it allows to compute a proof only once while convincing an unlimited number of verifiers. Popular interactive proof systems (e.g., 𝛴 -protocols) protect the witness through various properties (e.g., witness indistinguishability (WI) and zero knowledge (ZK)) but typically they are not publicly verifiable since such proofs are convincing only for those verifiers who contributed to the transcripts of the proofs. The only known proof systems that are publicly verifiable rely on a non-interactive (NI) prover, through trust assumptions (e.g., NIZK in the CRS model), heuristic assumptions (e.g., NIZK in the random oracle model), specific number-theoretic assumptions on bilinear groups or relying on obfuscation assumptions (obtaining NIWI with no setups). In this work we construct publicly verifiable witness-indistinguishable proof systems from any 𝛴 -protocol, based only on the existence of a very generic blockchain. The novelty of our approach is in enforcing a non-interactive verification (thus guaranteeing public verifiability) while allowing the prover to be interactive and talk to the blockchain (this allows us to circumvent the need of strong assumptions and setups). This opens interesting directions for the design of cryptographic protocols leveraging on blockchain technology.more » « less
-
Abstract Existing experimental demonstrations of quantum computational advantage have had the limitation that verifying the correctness of the quantum device requires exponentially costly classical computations. Here we propose and analyse an interactive protocol for demonstrating quantum computational advantage, which is efficiently classically verifiable. Our protocol relies on a class of cryptographic tools called trapdoor claw-free functions. Although this type of function has been applied to quantum advantage protocols before, our protocol employs a surprising connection to Bell’s inequality to avoid the need for a demanding cryptographic property called the adaptive hardcore bit, while maintaining essentially no increase in the quantum circuit complexity and no extra assumptions. Leveraging the relaxed cryptographic requirements of the protocol, we present two trapdoor claw-free function constructions, based on Rabin’s function and the Diffie–Hellman problem, which have not been used in this context before. We also present two independent innovations that improve the efficiency of our implementation and can be applied to other quantum cryptographic protocols. First, we give a scheme to discard so-called garbage bits, removing the need for reversibility in the quantum circuits. Second, we show a natural way of performing postselection that reduces the fidelity needed to demonstrate quantum advantage. Combining these results, we describe a blueprint for implementing our protocol on Rydberg atom-based quantum devices, using hardware-native operations that have already been demonstrated experimentally.more » « less
