Quantum Time Lower Bounds by Permutation Invariance

• URL: http://arxiv.org/abs/2606.05099v1
• Date: Wed, 03 Jun 2026 17:03:24 GMT
• Title: Quantum Time Lower Bounds by Permutation Invariance
• Abstract summary: We provide a framework to establish lower bounds on the quantum time complexity for testing permutation-invariant properties of quantum states.<n>As an application, we obtain a series of matching lower bounds when given sample access to the input quantum states.<n>To the best of our knowledge, this is the first method that allows us to systematically establish tight lower bounds on quantum time complexity.
• Score: 13.491187998442596
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Tight bounds on quantum sample complexity and quantum query complexity have been known for various computational problems in the literature, whereas tight bounds on quantum time complexity (i.e., the size of quantum circuits) remain unresolved. In this paper, we provide a framework to establish lower bounds on the quantum time complexity for testing permutation-invariant properties of quantum states, via a reduction from quantum sample complexity. As an application, we obtain a series of matching lower bounds when given sample access to the input quantum states, including: 1. The SWAP test due to Buhrman, Cleve, Watrous, and de Wolf (Phys. Rev. Lett. 2001) is time-optimal to estimate the purity $\operatorname{tr}(ρ^2)$ and the inner product $\operatorname{tr}(ρσ)$. 2. The Shift test due to Ekert, Alves, Oi, Horodecki, Horodecki, and Kwek (Phys. Rev. Lett. 2002) is time-optimal to estimate the high-order functionals $\operatorname{tr}(ρ^k)$. 3. The productness tester for multipartite pure states due to Harrow and Montanaro (J. ACM 2013) is time-optimal. 4. The LMR protocol due to Lloyd, Mohseni, and Rebentrost (Nat. Phys. 2014) is time-optimal to implement the reflection operator about a pure state. 5. The samplizer due to Wang and Zhang (IEEE Trans. Inf. Theory 2025) is time-optimal for pure states. 6. The estimator for pure-state trace distance and fidelity due to Wang and Zhang (ICALP 2026) is time-optimal. To the best of our knowledge, this is the first method that allows us to systematically establish tight lower bounds on quantum time complexity.

Related papers

• A Lower Bound Framework for Quantum Functional Estimation [13.491187998442596]
  We develop a unified framework for proving lower bounds for estimating functionals of $d$-dimensional quantum states.<n>The framework combines a Haar-random moment encoding process with moment matching and best approximation.
  arXiv  Detail & Related papers  (2026-08-03T17:59:11Z)
• Enhancing Kerr-Cat Qubit Coherence with Controlled Dissipation [64.05054054401175]
  Kerr-cat qubit (KCQ) is a bosonic quantum processor.<n>KCQs are experimentally compatible with on-chip architectures and high-fidelity operations.<n>We present direct evidence that the bit-flip time in a KCQ is limited by leakage out of the qubit manifold.
  arXiv  Detail & Related papers  (2025-11-02T17:58:36Z)
• Analytic and Stochastic Approach to Quantum Advantages in Ground State and Quantum State Preparation Problems [5.458506740538826]
  We study the problems of state preparation, ground state preparation and quantum state preparation.<n>We propose an analytic approach to a quantum algorithm which prepares the ground state for $n$qubit Hamiltonian that is represented by $textpoly(n)$ Pauli operators.
  arXiv  Detail & Related papers  (2025-10-02T01:17:22Z)
• Topological control of quantum speed limits [55.2480439325792]
  We show that even if the quantum state is completely dispersionless, QFI in this state remains momentum-resolved.<n>We find bounds on quantum speed limit which scales as $sqrt|C|$ in a (dispersionless) topological phase.
  arXiv  Detail & Related papers  (2025-07-21T18:00:07Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• 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)
• Quantum Speed Limit for Change of Basis [55.500409696028626]
  We extend the notion of quantum speed limits to collections of quantum states. For two-qubit systems, we show that the fastest transformation implements two Hadamards and a swap of the qubits simultaneously. For qutrit systems the evolution time depends on the particular type of the unbiased basis.
  arXiv  Detail & Related papers  (2022-12-23T14:10:13Z)
• 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)
• Learning k-qubit Quantum Operators via Pauli Decomposition [11.498089180181365]
  Motivated by the limited qubit capacity of current quantum systems, we study the quantum sample complexity of $k$-qubit quantum operators. We show that the quantum sample complexity of $k$-qubit quantum operations is comparable to the classical sample complexity of their counterparts.
  arXiv  Detail & Related papers  (2021-02-10T01:20:55Z)

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.