Measuring Less to Learn More: Quadratic Speedup in Learning Nonlinear Properties of Quantum States

Area of Science:

• Quantum Information Science
• Quantum Computing
• Quantum State Tomography

Background:

• Measuring nonlinear functionals of quantum states, like Tr(ρᵏO), is crucial in quantum information science.
• Traditional methods using sample access to quantum states (ρ) require a number of copies proportional to the order (k) of the functional.

Purpose of the Study:

• To establish a lower bound for measuring kth order nonlinear functionals of quantum states under sample access.
• To investigate if purified access to quantum states offers an advantage over sample access for this task.
• To develop a quantum algorithm that leverages purified access for improved measurement efficiency.

Main Methods:

• Rigorous establishment of a lower bound of O(k) copies for sample access.
• Development of a quantum algorithm utilizing purified access to quantum states.
• Application of optimal polynomial approximation theory, specifically Chebyshev polynomials, tailored for power functions.

Main Results:

• A lower bound of Θ(√k) copies is established for purified access, demonstrating a quadratic advantage over sample-based methods.
• The proposed quantum algorithm achieves this Θ(√k) bound, showcasing practical efficiency gains.
• A fundamental distinction between sample and purified access to quantum states is revealed.

Conclusions:

• Purified access to quantum states provides a significant quadratic speedup for measuring nonlinear functionals compared to sample access.
• The findings have broad implications for quantum entropies, quantum Fisher information, and other quantum information processing tasks.
• Optimal polynomial approximations are key technical innovations enabling this quantum advantage.