A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting

• URL: http://arxiv.org/abs/2512.01971v1
• Date: Mon, 01 Dec 2025 18:27:37 GMT
• Title: A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting
• Authors: Kean Chen, Qisheng Wang, Zhicheng Zhang,
• Abstract summary: In this paper, we compile a list of quantum lower and upper bounds for property testing that are obtained by quantum sample-to-query lifting.<n>The problems of interest include testing properties of probability distributions and quantum states, such as entropy and closeness.<n>In total, we present 49 complexity bounds, where 41 are new and 18 are (near-)optimal.
• Score: 33.25179630727782
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum sample-to-query lifting, a relation between quantum sample complexity and quantum query complexity presented in Wang and Zhang (SIAM J. Comput. 2025), was significantly strengthened by Tang, Wright, and Zhandry (2025) to the case of state-preparation oracles. In this paper, we compile a list of quantum lower and upper bounds for property testing that are obtained by quantum sample-to-query lifting. The problems of interest include testing properties of probability distributions and quantum states, such as entropy and closeness. This collection contains new results, as well as new proofs of known bounds. In total, we present 49 complexity bounds, where 41 are new and 18 are (near-)optimal.

Related papers

• Sample Complexity of Composite Quantum Hypothesis Testing [1.376408511310322]
  We characterize the sample complexity of symmetric composite binary quantum hypothesis testing.<n>Specifically, we derive lower bounds that generalize the sample complexity of simple QHT.<n>We extend our analysis to the differentially private setting, establishing the sample complexity for privacy-preserving composite QHT.
  arXiv  Detail & Related papers  (2026-01-13T14:15:12Z)
• Lower Bounds for Unitary Property Testing with Proofs and Advice [0.0]
  In unitary property testing a quantum algorithm, also known as a tester, is given query access to a black-box unitary.<n>We propose a new technique for proving lower bounds on the quantum query of unitary property testing.
  arXiv  Detail & Related papers  (2024-01-15T19:00:36Z)
• Taming Quantum Time Complexity [45.867051459785976]
  We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
  arXiv  Detail & Related papers  (2023-11-27T14:45:19Z)
• Quantum Lower Bounds by Sample-to-Query Lifting [33.82353457014144]
  We propose a new method for proving quantum query lower bounds by a quantum sample-to-query lifting theorem.<n>We provide unified proofs for some known lower bounds, including those for phase/amplitude estimation and Hamiltonian simulation.
  arXiv  Detail & Related papers  (2023-08-03T14:41:49Z)
• 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)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Unitary property testing lower bounds by polynomials [0.15229257192293197]
  We study unitary property testing, where a quantum algorithm is given query access to a black-box unitary. Characterizing the complexity of these problems requires new algorithmic techniques and lower bound methods. We present a unitary property testing-based approach towards an oracle separation between $mathsfQMA$ and $mathsfQMA(2)$.
  arXiv  Detail & Related papers  (2022-10-12T03:01:00Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• 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)

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.