On the Cryptographic Foundations of Interactive Quantum Advantage

• URL: http://arxiv.org/abs/2510.05082v1
• Date: Mon, 06 Oct 2025 17:51:22 GMT
• Title: On the Cryptographic Foundations of Interactive Quantum Advantage
• Authors: Kabir Tomer, Mark Zhandry,
• Abstract summary: hardness required to achieve proofs of quantumness (PoQ)<n>In particular, our results help explain the challenges in using lattices to build publicly verifiable PoQ.
• Score: 8.438148845727445
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, we study the hardness required to achieve proofs of quantumness (PoQ), which in turn capture (potentially interactive) quantum advantage. A ``trivial'' PoQ is to simply assume an average-case hard problem for classical computers that is easy for quantum computers. However, there is much interest in ``non-trivial'' PoQ that actually rely on quantum hardness assumptions, as these are often a starting point for more sophisticated protocols such as classical verification of quantum computation (CVQC). We show several lower-bounds for the hardness required to achieve non-trivial PoQ, specifically showing that they likely require cryptographic hardness, with different types of cryptographic hardness being required for different variations of non-trivial PoQ. In particular, our results help explain the challenges in using lattices to build publicly verifiable PoQ and its various extensions such as CVQC.

Related papers

• Cryptographic Characterization of Quantum Advantage [8.093227427119325]
  We show that inefficient-verifier of quantumness (IV-PoQ) exist if and only if classically-secure one-way puzzles (OWPuzzs) exist. This is the first time that a complete cryptographic characterization of quantum advantage is obtained.
  arXiv  Detail & Related papers  (2024-10-01T08:29:25Z)
• QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more [5.306949367777188]
  There are problems for which there is no trivial' computational advantage possible with the current quantum hardware.<n>We would like to have evidence that it is difficult to solve those problems on quantum computers; but what is their exact complexity?<n>By the use of the QSETH framework [Buhrman-Patro-Speelman 2021], we are able to understand the quantum complexity of a few natural variants of CNFSAT.
  arXiv  Detail & Related papers  (2023-09-28T13:30:20Z)
• Quantum Imitation Learning [74.15588381240795]
  We propose quantum imitation learning (QIL) with a hope to utilize quantum advantage to speed up IL. We develop two QIL algorithms, quantum behavioural cloning (Q-BC) and quantum generative adversarial imitation learning (Q-GAIL) Experiment results demonstrate that both Q-BC and Q-GAIL can achieve comparable performance compared to classical counterparts.
  arXiv  Detail & Related papers  (2023-04-04T12:47:35Z)
• Delegated variational quantum algorithms based on quantum homomorphic encryption [69.50567607858659]
  Variational quantum algorithms (VQAs) are one of the most promising candidates for achieving quantum advantages on quantum devices. The private data of clients may be leaked to quantum servers in such a quantum cloud model. A novel quantum homomorphic encryption (QHE) scheme is constructed for quantum servers to calculate encrypted data.
  arXiv  Detail & Related papers  (2023-01-25T07:00:13Z)
• Response to "Exponential challenges in unbiasing quantum Monte Carlo algorithms with quantum computers" [0.7943023838493659]
  We provide details and numerics to emphasize that the prospects for practical quantum advantage in QC-QMC remain open. The exponential challenges in QC-QMC are dependent on (1) the choice of QMC methods, (2) the underlying system, and (3) the form of trial and walker wavefunctions. Future research should aim to identify examples for which QC-QMC enables practical quantum advantage.
  arXiv  Detail & Related papers  (2022-07-27T20:17:11Z)
• Universal expressiveness of variational quantum classifiers and quantum kernels for support vector machines [0.0]
  We show that variational quantum classifiers (VQC) and support vector machines with quantum kernels (QSVM) can solve a classification problem based on the k-Forrelation problem. Our results imply that there exists a feature map and a quantum kernel that make VQC and QSVM efficient solvers for any BQP problem.
  arXiv  Detail & Related papers  (2022-07-12T22:03:31Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
  arXiv  Detail & Related papers  (2021-07-05T17:45:41Z)
• Efficient measure for the expressivity of variational quantum algorithms [72.59790225766777]
  We exploit an advanced tool in statistical learning theory, i.e., covering number, to study the expressivity of variational quantum algorithms. We first exhibit how the expressivity of VQAs with an arbitrary ansatze is upper bounded by the number of quantum gates and the measurement observable. We then explore the expressivity of VQAs on near-term quantum chips, where the system noise is considered.
  arXiv  Detail & Related papers  (2021-04-20T13:51:08Z)
• Towards understanding the power of quantum kernels in the NISQ era [79.8341515283403]
  We show that the advantage of quantum kernels is vanished for large size datasets, few number of measurements, and large system noise. Our work provides theoretical guidance of exploring advanced quantum kernels to attain quantum advantages on NISQ devices.
  arXiv  Detail & Related papers  (2021-03-31T02:41:36Z)
• Variational Quantum Algorithms [1.9486734911696273]
  Quantum computers promise to unlock applications such as large quantum systems or solving large-scale linear algebra problems. Currently available quantum devices have serious constraints, including limited qubit numbers and noise processes that limit circuit depth. Variational Quantum Algorithms (VQAs), which employ a classical simulation to train a parametrized quantum circuit, have emerged as a leading strategy to address these constraints.
  arXiv  Detail & Related papers  (2020-12-16T21:00:46Z)
• Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
  We propose a resource and runtime efficient scheme termed quantum architecture search (QAS) QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates. We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
  arXiv  Detail & Related papers  (2020-10-20T12:06:27Z)

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.