A Hierarchy for Replica Quantum Advantage

Abstract

We prove that given the ability to make entangled measurements on at most $k$ replicas of an $n$-qubit state $\rho$ simultaneously, there is a property of $\rho$ which requires at least order $2^n$ measurements to learn. However, the same property only requires one measurement to learn if we can make an entangled measurement over a number of replicas polynomial in $k,n$. Because the above holds for each positive integer $k$, we obtain a hierarchy of tasks necessitating progressively more replicas to be performed efficiently. We introduce a powerful proof technique to establish our results, and also use this to provide new bounds for testing the mixedness of a quantum state.

arXiv comment3+17 pages, 2 figures; v2: typos fixed

References in corpus (10)

• Quantum Computing in the NISQ era and beyond
• Measuring entanglement entropy through the interference of quantum many-body twins
• Quantum thermalization through entanglement in an isolated many-body system
• Information-theoretic bounds on quantum advantage in machine learning
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Measuring the Renyi entropy of a two-site Fermi-Hubbard model on a trapped ion quantum computer
• Quantum Algorithmic Measurement
• Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)
• Improved quantum data analysis
• Toward Instance-Optimal State Certification With Incoherent Measurements

Cited by in corpus (4)

• Challenges and Opportunities in Quantum Machine Learning
• Quantum advantage in learning from experiments
• Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix
• Lower Bounds for Learning Quantum States with Single-Copy Measurements