2026-07-24T17:51:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12067 2024-03-06T10:49:12Z ddc:004 open_access

Simpler Proofs of Quantumness Brakerski, Zvika Koppula, Venkata Vazirani, Umesh Vidick, Thomas Proof of Quantumness Random Oracle Learning with Errors A proof of quantumness is a method for provably demonstrating (to a classical verifier) that a quantum device can perform computational tasks that a classical device with comparable resources cannot. Providing a proof of quantumness is the first step towards constructing a useful quantum computer. There are currently three approaches for exhibiting proofs of quantumness: (i) Inverting a classically-hard one-way function (e.g. using Shor’s algorithm). This seems technologically out of reach. (ii) Sampling from a classically-hard-to-sample distribution (e.g. BosonSampling). This may be within reach of near-term experiments, but for all such tasks known verification requires exponential time. (iii) Interactive protocols based on cryptographic assumptions. The use of a trapdoor scheme allows for efficient verification, and implementation seems to require much less resources than (i), yet still more than (ii). In this work we propose a significant simplification to approach (iii) by employing the random oracle heuristic. (We note that we do not apply the Fiat-Shamir paradigm.) We give a two-message (challenge-response) proof of quantumness based on any trapdoor claw-free function. In contrast to earlier proposals we do not need an adaptive hard-core bit property. This allows the use of smaller security parameters and more diverse computational assumptions (such as Ring Learning with Errors), significantly reducing the quantum computational effort required for a successful demonstration. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zvika Brakerski and Venkata Koppula and Umesh Vazirani and Thomas Vidick 2020 Is Part Of LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2020.8 urn:nbn:de:0030-drops-120677 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.8 eng https://creativecommons.org/licenses/by/3.0/legalcode