Quantum Time Lower Bounds by Permutation Invariance
2026-06-03 • Computational Complexity
Computational ComplexityInformation Theory
AI summaryⓘ
The authors develop a new method to prove lower bounds on how much time it takes for quantum computers to test properties of quantum states, focusing on the size of quantum circuits. They apply this method to show that several well-known quantum algorithms, such as the SWAP test and the Shift test, are time-optimal, meaning no faster quantum circuit can do the same tasks. This includes tests for state purity, inner products, and other complex properties. Their work is the first to systematically establish these time efficiency limits, complementing previous results on quantum sample and query complexities.
quantum sample complexityquantum query complexityquantum time complexityquantum circuitspermutation-invariant propertiesSWAP testShift testpure quantum statestrace distancequantum property testing
Authors
Qisheng Wang
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.