Quantum Property Testing Achieves 49 Complexity Bounds, Including 41 Novel and 18 Near-Optimal Results

Property testing seeks to efficiently determine whether an object possesses a certain property, and recent advances connect how much data, samples, are needed to the number of direct questions, queries, required to assess this. Kean Chen from the University of Pennsylvania, Qisheng Wang from the University of Edinburgh, and Zhicheng Zhang from the University of Technology Sydney, present a comprehensive compilation of complexity bounds achieved through a technique called sample-to-query lifting, significantly extending earlier work on state-preparation oracles. This research establishes a robust framework for understanding the inherent limitations and possibilities of property testing, particularly for assessing characteristics of probability distributions and quantum states like entropy and closeness. The team delivers a total of 49 complexity bounds, with a substantial majority being entirely new results and a significant portion representing the best currently achievable limits for these types of tests.

The team achieved enhanced bounds for estimating von Neumann and Rényi entropy, as well as trace distance and fidelity, often by leveraging existing quantum query algorithms and refining their application through the sample-to-query framework.

Quantum Algorithms for Entropy and Fidelity Estimation

A significant body of work focuses on developing quantum algorithms for estimating quantum entropy, trace distance, and fidelity, demonstrating a very active area of research. Several papers explore quantum algorithms for entropy and distance estimation, including work by Wang and colleagues in 2024 and 2025, and by Wan in 2024 and 2025. Work by Zhandry and colleagues in 2023 also contributes to this area, focusing on quantum algorithms for fidelity estimation.

Researchers also investigate lower bounds on quantum computation, establishing limits on what quantum algorithms can achieve. These studies help define the boundaries of quantum computational power and guide the development of realistic algorithms.

Recent publications from 2023, 2024, and 2025 indicate a rapidly evolving field. YKS and colleagues in 2024 explore a one-to-one correspondence between deterministic port-based teleportation and unitary estimation, while ZWY and colleagues in 2024 present a parallel quantum algorithm for Hamiltonian simulation. These contributions, alongside others, demonstrate the breadth and depth of current research in quantum algorithms and complexity.

Sample Complexity and Quantum State Estimation

This work presents a comprehensive analysis of fundamental limits in property testing, specifically examining the relationship between sample and query complexity. Researchers significantly strengthened existing bounds using sample-to-query lifting, compiling a collection of 49 complexity bounds, with the majority being novel and a substantial number achieving near-optimal performance. The authors acknowledge that the established bounds are often dependent on the rank of the quantum state, and further research is needed to address the complexities of high-rank systems.

Notably, they achieved enhanced bounds for estimating von Neumann and Rényi entropy, as well as trace distance and fidelity, often by leveraging existing quantum query algorithms and refining their application through the sample-to-query framework. These results contribute to a more precise understanding of the resources required for characterizing quantum systems and assessing their properties.

Future work could focus on extending these techniques to a broader range of properties and exploring the limitations imposed by practical constraints, such as noise and decoherence. The team also suggests that continued investigation into the interplay between sample and query complexity will be crucial for developing more efficient quantum algorithms and advancing our understanding of fundamental limits in information processing.