The Knowledge Complexity of Quantum Problems

• URL: http://arxiv.org/abs/2510.06923v1
• Date: Wed, 08 Oct 2025 12:00:32 GMT
• Title: The Knowledge Complexity of Quantum Problems
• Authors: Giulio Malavolta,
• Abstract summary: We show that every quantum problem that is provable with an interactive protocol, is also provable in zero-knowledge.<n>Our protocol achieves unconditional soundness and computational zero-knowledge, under standard assumptions in cryptography.
• Score: 15.563172757398293
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Foundational results in theoretical computer science have established that everything provable, is provable in zero knowledge. However, this assertion fundamentally assumes a classical interpretation of computation and many interesting physical statements that one can hope to prove are not characterized. In this work, we consider decision problems, where the problem instance itself is specified by a (pure) quantum state. We discuss several motivating examples for this notion and, as our main technical result, we show that every quantum problem that is provable with an interactive protocol, is also provable in zero-knowledge. Our protocol achieves unconditional soundness and computational zero-knowledge, under standard assumptions in cryptography. In addition, we show how our techniques yield a protocol for the Uhlmann transformation problem that achieves a meaningful notion of zero-knowledge, also in the presence of a malicious verifier.

Related papers

• Few measurement shots challenge generalization in learning to classify entanglement [0.0]
  This paper focuses on hybrid quantum learning techniques where classical machine-learning methods are paired with quantum algorithms. We show that, in some settings, the uncertainty coming from a few measurement shots can be the dominant source of errors. We introduce an estimator based on classical shadows that performs better in the big data, few copy regime.
  arXiv  Detail & Related papers  (2024-11-10T21:20:21Z)
• Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem [70.42372213666553]
  The No-Free-Lunch (NFL) theorem quantifies problem- and data-independent generalization errors regardless of the optimization process. We categorize a diverse array of quantum learning algorithms into three learning protocols designed for learning quantum dynamics under a specified observable. Our derived NFL theorems demonstrate quadratic reductions in sample complexity across CLC-LPs, ReQu-LPs, and Qu-LPs. We attribute this performance discrepancy to the unique capacity of quantum-related learning protocols to indirectly utilize information concerning the global phases of non-orthogonal quantum states.
  arXiv  Detail & Related papers  (2024-05-12T09:05:13Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [88.57261102552016]
  The anticipated applications of quantum computers span across science and industry.<n>We present a survey of several potential application areas of quantum algorithms.<n>We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Unitary Complexity and the Uhlmann Transformation Problem [39.6823854861458]
  We introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes.<n>We use this framework to study the complexity of transforming one entangled state into another via local operations.<n>Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.
  arXiv  Detail & Related papers  (2023-06-22T17:46:39Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• Unclonability and Quantum Cryptanalysis: From Foundations to Applications [0.0]
  Unclonability is a fundamental concept in quantum theory and one of the main non-classical properties of quantum information. We introduce new notions of unclonability in the quantum world, namely quantum physical unclonability. We discuss several applications of this new type of unclonability as a cryptographic resource for designing provably secure quantum protocols.
  arXiv  Detail & Related papers  (2022-10-31T17:57:09Z)
• 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)
• A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds [12.525959293825318]
  We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box $epsilon$-zero-knowledge against quantum attacks. At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier.
  arXiv  Detail & Related papers  (2020-11-05T05:40:05Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• Quantum entanglement recognition [0.0]
  We formulate a framework for probing entanglement based on machine learning techniques. We show that the resulting quantum entanglement recognition task is accurate and can be assigned a well-controlled error.
  arXiv  Detail & Related papers  (2020-07-28T18:00:00Z)
• Classical proofs of quantum knowledge [10.432041176720842]
  We define the notion of a proof of knowledge in the setting where the verifier is classical. We show that, if a nondestructive classical proof of quantum knowledge exists for some state, then that state can be cloned by an adversary.
  arXiv  Detail & Related papers  (2020-05-04T17:45:21Z)
• Using Quantum Metrological Bounds in Quantum Error Correction: A Simple Proof of the Approximate Eastin-Knill Theorem [77.34726150561087]
  We present a proof of the approximate Eastin-Knill theorem, which connects the quality of a quantum error-correcting code with its ability to achieve a universal set of logical gates. Our derivation employs powerful bounds on the quantum Fisher information in generic quantum metrological protocols.
  arXiv  Detail & Related papers  (2020-04-24T17:58:10Z)

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.