TL;DR
This paper introduces novel, efficient quantum algorithms for estimating the trace distance between quantum states, a crucial measure of their distinguishability. The algorithms achieve significant speedups, especially for low-rank states, and are robust to noise, making them promising for practical quantum applications.
What Problem Does This Paper Address?
In quantum information, understanding how different quantum states can be distinguished is fundamental. The trace distance is a key metric for this, but efficiently calculating or estimating it, especially for mixed quantum states, has been a long-standing challenge. While classical methods exist, their computational cost scales exponentially with the number of qubits. Prior quantum algorithms for this task, particularly for low-rank states, had complexities that grew rapidly with the rank and desired precision. This paper aims to bridge this gap by developing quantum algorithms with significantly improved complexity, making trace distance estimation more practical.
Methods
The authors propose two main quantum algorithms:
- Purified Access Algorithm: This algorithm leverages "purified access" to quantum states, meaning they have access to quantum circuits that prepare the "purifications" of the states. The core technique involves using Quantum Singular Value Transformation (QSVT) to approximate the sign function and the Hadamard test to estimate specific expectation values. This approach leads to a query complexity of $\tilde{O}(r/\varepsilon^2)$, a significant improvement over previous methods.
- Sample Access Algorithm: This algorithm is derived from the purified access version by adapting it to work with "sample access," where only identical copies of the quantum states are available. This is achieved by using quantum channels to approximately implement the necessary unitary operations, a technique inspired by recent work on fidelity estimation. This algorithm boasts a sample complexity of $\tilde{O}(r^2/\varepsilon^5)$.
Both algorithms are designed to be independent of the dimension of the quantum states ($N$), with only a logarithmic factor dependence on $N$ in their time complexity.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Decomposition of Trace Distance: A key insight is the reformulation of the trace distance into two terms that can be estimated independently. This decomposition, based on the singular value decomposition of the difference between the two states, is central to their algorithmic approach.
- QSVT as a Powerful Tool: The paper effectively demonstrates the utility of Quantum Singular Value Transformation (QSVT) for approximating the sign function, a crucial step in their trace distance estimation. This highlights QSVT's versatility beyond its initial applications.
- Bridging Purified and Sample Access: The authors show a clever way to adapt algorithms designed for purified access to the more practical scenario of sample access by employing quantum channels for approximate implementation of unitary operations. This is a common theme in quantum algorithm development, and their specific implementation is noteworthy.
- BQP-Completeness: The paper proves that the decision version of low-rank trace distance estimation is BQP-complete. This is a strong theoretical result, implying that efficient classical algorithms for this problem are unlikely unless P=BPP.
Key Results
- Purified Access Algorithm: Achieves a query complexity of $\tilde{O}(r/\varepsilon^2)$, a linear dependence on the rank $r$, and is independent of the state dimension $N$.
- Sample Access Algorithm: Achieves a sample complexity of $\tilde{O}(r^2/\varepsilon^5)$, also with a linear dependence on $r$ and independence from $N$.
- Time Complexity: Both algorithms have time complexities that scale as $\tilde{O}(\text{query/sample complexity} \cdot \log N)$.
- BQP-Completeness: The decision problem of low-rank trace distance estimation is shown to be BQP-complete.
- Robustness: The algorithms are shown to be applicable to approximately low-rank quantum states, making them more robust to noise and imperfections.
Limitations and Future Work
- Low-Rank Assumption: While the algorithms are extended to approximately low-rank states, they still rely on some notion of "low-rankness" or bounded eigenvalue sums. The paper explores how this condition can be met for various scenarios (e.g., noisy states, Gibbs states), but it remains a core assumption.
- Open Problems: The authors identify several open problems, including:
- Investigating sublinear dependence on rank for trace distance and fidelity estimation.
- Developing shallower quantum circuits for these tasks.
- Tightening the gap between known quantum lower and upper bounds for trace distance and fidelity estimation.
- Exploring further applications of their techniques beyond trace distance estimation.
Summary updated