mlsanityData to 14 Oct 2026

A Hierarchy for Replica Quantum Advantage

arXiv 2111.05874 ↗First posted 10 Nov 2021quant-ph cs.CC cs.ITcited by 16

Not on the map. Why?

Abstract (arXiv)

We prove that given the ability to make entangled measurements on at most k replicas of an n-qubit state ρ simultaneously, there is a property of ρ which requires at least order 2n 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.

Key facts. Cited by 16 papers in the map (data through 14 Oct 2026). Builds on 3 of its 25 references that are in the map. First posted on arXiv 10 Nov 2021.

Builds on

3 of 25 references.

References · 3

  1. 2021Information-theoretic bounds on quantum advantage in machine learningcited by 96
  2. 2020Entanglement is Necessary for Optimal Quantum Property Testingcited by 23
  3. 2021Toward Instance-Optimal State Certification With Incoherent Measurementscited by 12

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 7; 2023: 1; 2024: 4; 2025: 3.

16 papers.

Sort:

  1. 2023Challenges and Opportunities in Quantum Machine Learningcited by 203
  2. 2021Quantum advantage in learning from experimentscited by 188
  3. 2022Out-of-distribution generalization for learning quantum dynamicscited by 49
  4. 2022Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrixcited by 23
  5. 2022The Complexity of NISQcited by 13
  6. 2022Foundations for learning from noisy quantum experimentscited by 12
  7. 2022When Does Adaptivity Help for Quantum State Learning?cited by 12
  8. 2025A Primer on Quantum Machine Learningcited by 12
  9. 2022Tight Bounds for Quantum State Certification with Incoherent Measurementscited by 11
  10. 2022Lower Bounds for Learning Quantum States with Single-Copy Measurementscited by 8
  11. 2024On the sample complexity of purity and inner product estimationcited by 5
  12. 2024An optimal tradeoff between entanglement and copy complexity for state tomographycited by 3
4 more
  1. 2024Learning topological states from randomized measurements using variational tensor network tomographycited by 3
  2. 2024A Parameter-Efficient Quantum Anomaly Detection Method on a Superconducting Quantum Processorcited by 2
  3. 2025Instance-Optimal Quantum State Certification with Entangled Measurementscited by 1
  4. 2025Non-iid hypothesis testing: from classical to quantumcited by 0