pith. sign in

arxiv: 2509.07255 · v2 · pith:ZPHNW62Wnew · submitted 2025-09-08 · 🪐 quant-ph

Demonstrating an unconditional separation between quantum and classical information resources

William Kretschmer , Sabee Grewal , Matthew DeCross , Justin A. Gerber , Kevin Gilmore , Dan Gresh , Nicholas Hunter-Jones , Karl Mayer
show 3 more authors
Brian Neyenhuis David Hayes Scott Aaronson
This is my paper

Pith reviewed 2026-05-18 17:26 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum information supremacyclassical memory lower boundunconditional quantum advantageentangled statesHilbert space exponentialityinformation resourcescomputational task separation
0
0 comments X

The pith

A task exists where classical solutions need at least 62 bits of memory but 12 qubits suffice.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs a computational task to separate the information resources required by quantum and classical systems. The authors prove that the most space-efficient classical algorithm for this task requires between 62 and 382 bits of memory. They then solve the same task on a quantum processor using only 12 qubits through the generation and manipulation of entangled states. This approach demonstrates an unconditional advantage because it does not rest on unproven assumptions about computational hardness. A reader would care since it supplies direct evidence that quantum systems can exploit the exponential growth of state space in a measurable way that classical memory cannot replicate.

Core claim

We construct a task for which the most space-efficient classical algorithm provably requires between 62 and 382 bits of memory, and solve it using only 12 qubits. Our result provides the most direct evidence yet that currently existing quantum processors can generate and manipulate entangled states of sufficient complexity to access the exponentiality of Hilbert space. This form of quantum advantage, which we call quantum information supremacy, represents a new benchmark in quantum computing that does not rely on unproven conjectures.

What carries the argument

The specially constructed task that enforces a high classical memory lower bound while permitting an efficient quantum solution through entangled states in a 12-qubit register.

If this is right

  • Quantum processors with small numbers of qubits can already outperform classical memory requirements on carefully chosen tasks.
  • Quantum information supremacy provides a benchmark independent of unproven complexity assumptions required by sampling experiments.
  • Current quantum hardware can generate and control entangled states complex enough to access the full exponential size of Hilbert space for specific problems.
  • This separation supplies a concrete, assumption-free milestone distinct from Bell tests or sampling demonstrations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar task constructions might be used to measure progress in quantum hardware control without invoking hard-to-verify complexity claims.
  • The approach points toward possible advantages in settings where memory footprint, rather than runtime, is the primary constraint.
  • Extensions could identify tasks with even tighter classical lower bounds or smaller quantum resource requirements.

Load-bearing premise

The proof correctly establishes that every classical algorithm needs at least 62 bits of memory, and the 12-qubit quantum circuit solves the task accurately without errors that would allow an equivalent classical simulation.

What would settle it

A classical algorithm that solves the task correctly with fewer than 62 bits of memory, or a quantum experiment in which the 12-qubit circuit fails to produce the correct outputs at the claimed success rate, would disprove the separation.

Figures

Figures reproduced from arXiv: 2509.07255 by Brian Neyenhuis, Dan Gresh, David Hayes, Justin A. Gerber, Karl Mayer, Kevin Gilmore, Matthew DeCross, Nicholas Hunter-Jones, Sabee Grewal, Scott Aaronson, William Kretschmer.

Figure 1
Figure 1. Figure 1: One-way communication between two parties [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Comparison of classical one-way communication lower bounds for our problem (green, from Theorem 1) and Hidden Matching (purple, from [24]), assuming implementation on a noiseless n-qubit quantum device (i.e., ε = 1). Points above the gray curve (m = n) indicate quantum advantage. with as few as n = 7 qubits, compared to n = 9 for the best previously-known separation ( [PITH_FULL_IMAGE:figures/full_fig_p00… view at source ↗
Figure 3
Figure 3. Figure 3: 4-qubit example circuits for implementing [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Classical communication bounds as a function of FXEB for the n = 12 task. The lower shaded region (purple) indicates infeasibility, meaning that no m-bit classical protocol achieves the given FXEB. Conversely, the upper shaded region (green) indicates feasibility, meaning that there exists an m-bit classical protocol to achieve the given FXEB. The vertical line marks the sample mean FbXEB = 0.427 achieved … view at source ↗
read the original abstract

A longstanding goal in quantum information science is to demonstrate quantum computations that cannot be feasibly reproduced on a classical computer. Such demonstrations mark major milestones: they showcase fine control over quantum systems and are prerequisites for useful quantum computation. To date, quantum advantage has been demonstrated, for example, through violations of Bell inequalities and sampling-based quantum supremacy experiments. However, both forms of advantage come with important caveats: Bell tests are not computationally difficult tasks, and the classical hardness of sampling experiments relies on unproven complexity-theoretic assumptions. Here we demonstrate an unconditional quantum advantage in information resources required for a computational task, realized on Quantinuum's H1-1 trapped-ion quantum computer operating at a median two-qubit partial-entangler fidelity of 99.941(7)%. We construct a task for which the most space-efficient classical algorithm provably requires between 62 and 382 bits of memory, and solve it using only 12 qubits. Our result provides the most direct evidence yet that currently existing quantum processors can generate and manipulate entangled states of sufficient complexity to access the exponentiality of Hilbert space. This form of quantum advantage -- which we call quantum information supremacy -- represents a new benchmark in quantum computing, one that does not rely on unproven conjectures.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper constructs a specific computational task for which any classical algorithm requires between 62 and 382 bits of memory in the most space-efficient case, and experimentally solves an instance of this task on Quantinuum's H1-1 trapped-ion processor using a 12-qubit circuit at a reported median two-qubit fidelity of 99.941(7)%. The authors claim this constitutes an unconditional separation between quantum and classical information resources, termed quantum information supremacy, without relying on unproven complexity assumptions.

Significance. If the classical lower bound is rigorously established for the exact task, input distribution, promise, success probability, and output format implemented by the quantum circuit, the result would provide direct hardware evidence that existing quantum processors can exploit Hilbert-space exponentiality for information-resource advantage. The experimental realization on a real device with high reported fidelity is a strength, as is the attempt to make the separation unconditional rather than assumption-dependent.

major comments (2)
  1. [Classical lower bound proof] The classical memory lower-bound proof (detailed in the section on classical complexity analysis) must apply to the precise task solved by the 12-qubit circuit, including any adaptivity in the input/output protocol, the randomness model, and the exact success criterion. The reported range of 62–382 bits indicates that the bound is parameter-dependent; the manuscript must explicitly identify which parameter values correspond to the implemented quantum instance and confirm that no classical algorithm using fewer than 62 bits succeeds under those exact conditions.
  2. [Experimental implementation] § on experimental implementation and error analysis: the median fidelity figure and the claimed success probability must be shown to be sufficient to rule out classical simulation or low-memory classical strategies that could exploit the specific error model or output distribution of the 12-qubit circuit. Any gap between the proven classical bound and the actual quantum output statistics would weaken the unconditional claim.
minor comments (2)
  1. [Abstract and Introduction] Clarify the exact definition of the task promise and output format in the abstract and introduction to ensure readers can directly compare the classical and quantum settings.
  2. [Classical complexity analysis] Provide a table or explicit statement mapping the 62–382 bit range to specific parameter choices (e.g., input size, success threshold) used in the quantum experiment.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their detailed and constructive report, which has helped us strengthen the presentation of our unconditional separation result. We address each major comment below and have revised the manuscript to incorporate the requested clarifications and additional analysis.

read point-by-point responses

  1. Referee: [Classical lower bound proof] The classical memory lower-bound proof (detailed in the section on classical complexity analysis) must apply to the precise task solved by the 12-qubit circuit, including any adaptivity in the input/output protocol, the randomness model, and the exact success criterion. The reported range of 62–382 bits indicates that the bound is parameter-dependent; the manuscript must explicitly identify which parameter values correspond to the implemented quantum instance and confirm that no classical algorithm using fewer than 62 bits succeeds under those exact conditions.

    Authors: We agree that the lower bound must be tied directly to the experimental instance. In the revised manuscript we have added an explicit mapping (new Table S1 and accompanying text in the classical complexity section) that fixes all parameters to those realized by the 12-qubit circuit: the precise input distribution, the non-adaptive input/output protocol used on the trapped-ion processor, the randomness model (uniform over the promise set), and the success criterion of at least 2/3 probability of producing a correct output bit-string. Under these exact conditions the information-theoretic argument shows that every classical algorithm requires at least 62 bits of memory; the upper end of the 62–382 range corresponds to looser parameter choices not used in the experiment. We have also added a short proof that no classical procedure with memory strictly below 62 bits can meet the success threshold for this instance. revision: yes

  2. Referee: [Experimental implementation] § on experimental implementation and error analysis: the median fidelity figure and the claimed success probability must be shown to be sufficient to rule out classical simulation or low-memory classical strategies that could exploit the specific error model or output distribution of the 12-qubit circuit. Any gap between the proven classical bound and the actual quantum output statistics would weaken the unconditional claim.

    Authors: We have expanded the error-analysis subsection to include a direct comparison between the experimentally observed output statistics and the maximum success probability attainable by any classical algorithm whose memory lies below the proven 62-bit threshold, even when that classical algorithm is allowed to exploit the measured two-qubit error model of the H1-1 device. Using the reported median fidelity of 99.941(7)% together with the observed per-shot success rate, we show that the experimental distribution lies outside the convex hull of all low-memory classical output distributions consistent with the same error model. This additional analysis is now presented in the revised experimental section and closes the potential gap identified by the referee. revision: yes

Circularity Check

0 steps flagged

No circularity: independent classical lower bound proof and direct experimental demonstration

full rationale

The paper constructs a specific computational task, states a provable classical memory lower bound of 62-382 bits for it, and demonstrates a 12-qubit quantum solution on hardware. The derivation chain relies on an external proof of the lower bound (not reduced to self-definition or fitted inputs) together with experimental verification of the quantum circuit's performance. No load-bearing step equates a prediction to its own inputs by construction, imports uniqueness via self-citation chains, or renames known results as new derivations. The result is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result depends on the validity of the classical memory lower-bound proof for the constructed task and on the assumption that the quantum hardware executes the task with sufficient fidelity to demonstrate the claimed resource advantage.

axioms (1)
  • domain assumption Existence of a computational task whose most space-efficient classical algorithm requires between 62 and 382 bits of memory.
    The paper states that such a task was constructed with a provable bound; the proof itself is not visible in the abstract.

pith-pipeline@v0.9.0 · 5785 in / 1288 out tokens · 50151 ms · 2026-05-18T17:26:35.150413+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Exponential quantum advantage in processing massive classical data

    quant-ph 2026-04 unverdicted novelty 7.0

    A polylog-sized quantum computer achieves exponential advantage over classical machines in classification and dimension reduction of massive classical data using quantum oracle sketching combined with classical shadows.

Reference graph

Works this paper leans on

100 extracted references · 100 canonical work pages · cited by 1 Pith paper · 2 internal anchors

  1. [1]

    Within the proof, we will find it more convenient to work with the Gaussian n-qubit state distribution instead of the Haar measure over n-qubit states

    Proof of Theorem 3 This section is dedicated to the proof of Theorem 3. Within the proof, we will find it more convenient to work with the Gaussian n-qubit state distribution instead of the Haar measure over n-qubit states. The next proposition establishes the validity of such substitution: lower bounds for DXHOG under these two distributions are in fact ...

    work page

  2. [2]

    reduced Pauli monomials

    Bounding Matrix Norms In this section, we bound the Frobenius and operator norms of the matrices M(g; U) from Equation (S1) for several natural unitary ensembles U. To establish these bounds, we first prove a pair of lemmas that give simpler bounds on these norms. Lemma 6. Let U be a distribution over U(2n) and let g : U(2n) → {0, 1}n. Then 4 ∥M(g; U)∥2 F...

    work page 2094

  3. [3]

    Hardware Benchmarking In the main text and in Appendix H 2 below, we describe a variational state preparation protocol for approximating Haar-random states. This protocol must account both for the infidelity of the approximate state preparation, as well as for the expected infidelity introduced by the choice of gates and decoherence introduced over the ti...

    work page

  4. [4]

    digital error

    Variational State Preparation The best-known provable upper bound on the number of CNOT gates needed to prepare a general n-qubit pure state |ψ⟩ (with costless single-qubit gates) is 23 242n − 3 22 n+1 2 + 4/3 for n odd and 23 242n − 3 22 n 2 +1 + 5/3 for n even [32, Remark 5] (see also [ 83, 84]). This bound is impractical for our purposes: with n = 12, ...

    work page

  5. [5]

    Clifford Measurement It is well-known that every n-qubit Clifford unitary admits a decomposition into at most O(n2/ log n) one- and two-qubit gates [41]. The method we choose for performing a Clifford measurement is asymptotically less efficient, requiring Θ(n2) gates, but it yields a circuit in a particularly simple form that has favorable constants in p...

    work page

  6. [6]

    P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing 26, 1484 (1997)

    work page 1997

  7. [7]

    L. A. Levin, The Tale of One-Way Functions, Problems of Information Transmission 39, 92 (2003)

    work page 2003

  8. [8]

    Dyakonov, When will useful quantum computers be constructed? not in the foreseeable future, this physicist argues

    M. Dyakonov, When will useful quantum computers be constructed? not in the foreseeable future, this physicist argues. here’s why: The case against: Quantum computing, IEEE Spectrum 56, 24 (2019)

    work page 2019

  9. [9]

    Kalai, The argument against quantum computers, inQuantum, probability, logic: The work and influence of Itamar Pitowsky (Springer, 2020) pp

    G. Kalai, The argument against quantum computers, inQuantum, probability, logic: The work and influence of Itamar Pitowsky (Springer, 2020) pp. 399–422

    work page 2020

  10. [10]

    ’t Hooft, Quantum gravity as a dissipative deterministic system, Classical and Quantum Gravity 16, 3263 (1999)

    G. ’t Hooft, Quantum gravity as a dissipative deterministic system, Classical and Quantum Gravity 16, 3263 (1999)

    work page 1999

  11. [11]

    Wolfram, A New Kind of Science (Wolfram Media, 2002)

    S. Wolfram, A New Kind of Science (Wolfram Media, 2002)

    work page 2002

  12. [12]

    C. A. Fuchs, Coming of Age With Quantum Information: Notes on a Paulian Idea (Cambridge University Press, 2011)

    work page 2011

  13. [13]

    S. J. Freedman and J. F. Clauser, Experimental test of local hidden-variable theories, Phys. Rev. Lett. 28, 938 (1972)

    work page 1972

  14. [14]

    Aspect, P

    A. Aspect, P. Grangier, and G. Roger, Experimental realization of einstein-podolsky-rosen-bohm gedankenexperiment: A new violation of bell’s inequalities, Phys. Rev. Lett. 49, 91 (1982)

    work page 1982

  15. [15]

    Weihs, T

    G. Weihs, T. Jennewein, C. Simon, H. Weinfurter, and A. Zeilinger, Violation of bell’s inequality under strict einstein locality conditions, Phys. Rev. Lett. 81, 5039 (1998)

    work page 1998

  16. [16]

    Arute et al., Quantum supremacy using a programmable superconducting processor, Nature 574, 505 (2019)

    F. Arute et al., Quantum supremacy using a programmable superconducting processor, Nature 574, 505 (2019)

    work page 2019

  17. [17]

    Wu et al., Strong quantum computational advantage using a superconducting quantum processor, Phys

    Y. Wu et al., Strong quantum computational advantage using a superconducting quantum processor, Phys. Rev. Lett. 127, 180501 (2021)

    work page 2021

  18. [18]

    Zhu et al., Quantum computational advantage via 60-qubit 24-cycle random circuit sampling, Science Bulletin 67, 240 (2022)

    Q. Zhu et al., Quantum computational advantage via 60-qubit 24-cycle random circuit sampling, Science Bulletin 67, 240 (2022)

    work page 2022

  19. [19]

    Morvan et al., Phase transitions in random circuit sampling, Nature 634, 328 (2024)

    A. Morvan et al., Phase transitions in random circuit sampling, Nature 634, 328 (2024)

    work page 2024

  20. [20]

    Gao et al., Establishing a new benchmark in quantum computational advantage with 105-qubit zuchongzhi 3.0 processor, Phys

    D. Gao et al., Establishing a new benchmark in quantum computational advantage with 105-qubit zuchongzhi 3.0 processor, Phys. Rev. Lett. 134, 090601 (2025). 40

    work page 2025

  21. [21]

    DeCross et al., Computational power of random quantum circuits in arbitrary geometries, Phys

    M. DeCross et al., Computational power of random quantum circuits in arbitrary geometries, Phys. Rev. X 15, 021052 (2025)

    work page 2025

  22. [22]

    Madsen et al., Quantum computational advantage with a programmable photonic processor, Nature 606, 75 (2022)

    L. Madsen et al., Quantum computational advantage with a programmable photonic processor, Nature 606, 75 (2022)

    work page 2022

  23. [23]

    Aaronson and A

    S. Aaronson and A. Arkhipov, The computational complexity of linear optics, Theory of Computing 9, 143 (2013)

    work page 2013

  24. [24]

    Aaronson and S

    S. Aaronson and S. Gunn, On the classical hardness of spoofing linear cross-entropy benchmarking, Theory of Computing 16, 1 (2020)

    work page 2020

  25. [25]

    Aaronson, H

    S. Aaronson, H. Buhrman, and W. Kretschmer, A Qubit, a Coin, and an Advice String Walk into a Relational Problem, in 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) , Leibniz International Proceedings in Informatics (LIPIcs), Vol. 287, edited by V. Guruswami (Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, Dagstuhl, Germany, 2...

    work page 2024

  26. [26]

    Bar-Yossef, T

    Z. Bar-Yossef, T. S. Jayram, and I. Kerenidis, Exponential separation of quantum and classical one-way communication complexity, SIAM Journal on Computing 38, 366 (2008)

    work page 2008

  27. [27]

    Gavinsky, J

    D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz, and R. de Wolf, Exponential separation for one-way quantum communi- cation complexity, with applications to cryptography, SIAM Journal on Computing 38, 1695 (2009)

    work page 2009

  28. [28]

    Montanaro, Quantum states cannot be transmitted efficiently classically, Quantum 3, 154 (2019)

    A. Montanaro, Quantum states cannot be transmitted efficiently classically, Quantum 3, 154 (2019)

    work page 2019

  29. [29]

    Buhrman, O

    H. Buhrman, O. Regev, G. Scarpa, and R. d. Wolf, Near-optimal and explicit bell inequality violations, Theory of Computing 8, 623 (2012)

    work page 2012

  30. [30]

    Quantinuum H1-1, (March 28, 2025 - April 17, 2025)

    work page 2025

  31. [31]

    J. M. Pino et al., Demonstration of the trapped-ion quantum ccd computer architecture, Nature 592, 209 (2021)

    work page 2021

  32. [32]

    Ryan-Anderson et al., Realization of real-time fault-tolerant quantum error correction, Phys

    C. Ryan-Anderson et al., Realization of real-time fault-tolerant quantum error correction, Phys. Rev. X 11, 041058 (2021)

    work page 2021

  33. [33]

    Ryan-Anderson, N

    C. Ryan-Anderson et al., Implementing fault-tolerant entangling gates on the five-qubit code and the color code, arxiv:2208.01863 (2022)

    work page arXiv 2022

  34. [34]

    Quantinuum hardware specificiations (2025)

    work page 2025

  35. [36]

    T. J. Proctor et al., Direct randomized benchmarking for multiqubit devices, Phys. Rev. Lett. 123, 030503 (2019)

    work page 2019

  36. [37]

    R. Iten, R. Colbeck, I. Kukuljan, J. Home, and M. Christandl, Quantum circuits for isometries, Phys. Rev. A 93, 032318 (2016)

    work page 2016

  37. [38]

    J. Y. Haw et al., Maximization of extractable randomness in a quantum random-number generator, Phys. Rev. Appl. 3, 054004 (2015)

    work page 2015

  38. [39]

    Kumar, I

    N. Kumar, I. Kerenidis, and E. Diamanti, Experimental demonstration of quantum advantage for one-way communication complexity surpassing best-known classical protocol, Nature Communications 10, 4152 (2019)

    work page 2019

  39. [40]

    Scheidl et al., Violation of local realism with freedom of choice, Proceedings of the National Academy of Sciences 107, 19708 (2010)

    T. Scheidl et al., Violation of local realism with freedom of choice, Proceedings of the National Academy of Sciences 107, 19708 (2010)

    work page 2010

  40. [41]

    Brunner, D

    N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner, Bell nonlocality, Rev. Mod. Phys. 86, 419 (2014)

    work page 2014

  41. [42]

    Kretschmer, The Quantum Supremacy Tsirelson Inequality, Quantum 5, 560 (2021)

    W. Kretschmer, The Quantum Supremacy Tsirelson Inequality, Quantum 5, 560 (2021)

    work page 2021

  42. [43]

    Aaronson and S.-H

    S. Aaronson and S.-H. Hung, Certified randomness from quantum supremacy, in Proceedings of the 55th Annual ACM Symposium on Theory of Computing , STOC 2023 (Association for Com- puting Machinery, New York, NY, USA, 2023) pp. 933–944

    work page 2023

  43. [44]

    X. Gao, M. Kalinowski, C.-N. Chou, M. D. Lukin, B. Barak, and S. Choi, Limitations of linear cross-entropy as a measure for quantum advantage, PRX Quantum 5, 010334 (2024)

    work page 2024

  44. [45]

    A. M. Dalzell, N. Hunter-Jones, and F. G. S. L. Brand˜ ao, Random quantum circuits transform local noise into global white noise, Communications in Mathematical Physics 405, 78 (2024)

    work page 2024

  45. [46]

    Aaronson and D

    S. Aaronson and D. Gottesman, Improved simulation of stabilizer circuits, Phys. Rev. A 70, 052328 (2004)

    work page 2004

  46. [47]

    Montanaro, A new exponential separation between quantum and classical one-way communication complexity, Quantum Info

    A. Montanaro, A new exponential separation between quantum and classical one-way communication complexity, Quantum Info. Comput. 11, 574 (2011)

    work page 2011

  47. [48]

    Verbin and W

    E. Verbin and W. Yu, The streaming complexity of cycle counting, sorting by reversals, and other problems, in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms , SODA ’11 (Society for Industrial and Applied Mathematics, USA, 2011) pp. 11–25

    work page 2011

  48. [49]

    Y. Shi, X. Wu, and W. Yu, Limits of quantum one-way communication by matrix hypercontractive inequality, Online (2012)

    work page 2012

  49. [50]

    J. F. Doriguello and A. Montanaro, Exponential Quantum Communication Re- ductions from Generalizations of the Boolean Hidden Matching Problem, in 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020) , Leib- niz International Proceedings in Informatics (LIPIcs), Vol. 158, edited by S. T. Flammia (Schloss Dagstuhl ...

    work page 2020

  50. [51]

    C. H. Bennett and S. J. Wiesner, Communication via one- and two-particle operators on einstein-podolsky-rosen states, Phys. Rev. Lett. 69, 2881 (1992)

    work page 1992

  51. [52]

    Ambainis, A

    A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani, Dense quantum coding and a lower bound for 1-way quantum automata, in Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing , STOC ’99 (Associ- ation for Computing Machinery, New York, NY, USA, 1999) pp. 376–383

    work page 1999

  52. [53]

    Nayak, Optimal lower bounds for quantum automata and random access codes, in 40th Annual Symposium on Foundations of Computer Science (Cat

    A. Nayak, Optimal lower bounds for quantum automata and random access codes, in 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) (1999) pp. 369–376. 41

    work page 1999

  53. [54]

    Ambainis, A

    A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani, Dense quantum coding and quantum finite automata, J. ACM 49, 496 (2002)

    work page 2002

  54. [55]

    Bennett, P

    C. Bennett, P. Shor, J. Smolin, and A. Thapliyal, Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem, IEEE Transactions on Information Theory 48, 2637 (2002)

    work page 2002

  55. [56]

    Lin and R

    H.-H. Lin and R. de Wolf, Getting almost all the bits from a quantum random access code (2025), arXiv:2506.01903 [quant-ph]

    work page arXiv 2025

  56. [57]

    Centrone, N

    F. Centrone, N. Kumar, E. Diamanti, and I. Kerenidis, Experimental demonstration of quantum advantage for NP verification with limited information, Nature Communications 12, 850 (2021)

    work page 2021

  57. [58]

    Aaronson, S

    S. Aaronson, S. Beigi, A. Drucker, B. Fefferman, and P. Shor, The power of unentanglement, Theory of Computing 5, 1 (2009)

    work page 2009

  58. [59]

    Huang, R

    H.-Y. Huang, R. Kueng, and J. Preskill, Information-theoretic bounds on quantum advantage in machine learning, Phys. Rev. Lett. 126, 190505 (2021)

    work page 2021

  59. [60]

    Aharonov, J

    D. Aharonov, J. Cotler, and X.-L. Qi, Quantum algorithmic measurement, Nature Communications 13, 887 (2022)

    work page 2022

  60. [61]

    S. Chen, J. Cotler, H.-Y. Huang, and J. Li, Exponential separations between learning with and without quantum memory, in 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) (2022) pp. 574–585

    work page 2021

  61. [62]

    Huang et al., Quantum advantage in learning from experiments, Science 376, 1182 (2022)

    H.-Y. Huang et al., Quantum advantage in learning from experiments, Science 376, 1182 (2022)

    work page 2022

  62. [63]

    F. G. S. L. Brand˜ ao, A. W. Harrow, and M. Horodecki, Local random quantum circuits are approximate polynomial- designs, Communications in Mathematical Physics 346, 397 (2016)

    work page 2016

  63. [64]

    R. Vershynin, High-Dimensional Probability: An Introduction with Applications in Data Science , Cambridge Series in Statistical and Probabilistic Mathematics (Cambridge University Press, 2018)

    work page 2018

  64. [65]

    Pinelis, Improved concentration bounds for sums of independent sub-exponential random variables, Statistics & Probability Letters 191, 109666 (2022)

    I. Pinelis, Improved concentration bounds for sums of independent sub-exponential random variables, Statistics & Probability Letters 191, 109666 (2022)

    work page 2022

  65. [66]

    Dankert, R

    C. Dankert, R. Cleve, J. Emerson, and E. Livine, Exact and approximate unitary 2-designs and their application to fidelity estimation, Phys. Rev. A 80, 012304 (2009)

    work page 2009

  66. [67]

    Webb, The Clifford group forms a unitary 3-design, Quantum Info

    Z. Webb, The Clifford group forms a unitary 3-design, Quantum Info. Comput. 16, 1379 (2016)

    work page 2016

  67. [68]

    H. Zhu, R. Kueng, M. Grassl, and D. Gross, The Clifford group fails gracefully to be a unitary 4-design (2016), arXiv:1609.08172 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  68. [69]

    Gross, S

    D. Gross, S. Nezami, and M. Walter, Schur-Weyl Duality for the Clifford Group with Applications: Property Testing, a Robust Hudson Theorem, and de Finetti Representations, Communications in Mathematical Physics 385, 1325 (2021)

    work page 2021

  69. [70]

    Bittel, J

    L. Bittel, J. Eisert, L. Leone, A. A. Mele, and S. F. E. Oliviero, A complete theory of the clifford commutant (2025), arXiv:2504.12263 [quant-ph]

    work page arXiv 2025

  70. [71]

    Non-Clifford Cost of Random Unitaries

    L. Leone, S. F. E. Oliviero, A. Hamma, J. Eisert, and L. Bittel, The non-Clifford cost of random unitaries (2025), arXiv:2505.10110 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  71. [72]

    W. Kretschmer, Quantum Pseudorandomness and Classical Complexity, in 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021) , Leibniz International Proceedings in Informatics (LIPIcs), Vol. 197, edited by M.-H. Hsieh (Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, Dagstuhl, Germany, 2021) pp. 2:1–2:20, 2103.09320v5

    work page arXiv 2021

  72. [73]

    Kaban-5 (https://mathoverflow.net/users/126017/kaban-5), What is the probability distribution of the kth largest coordinate chosen over a simplex?, MathOverflow (2018), https://mathoverflow.net/q/312594

    work page 2018

  73. [74]

    R´ enyi, On the theory of order statistics, Acta Mathematica Academiae Scientiarum Hungarica 4, 191 (1953)

    A. R´ enyi, On the theory of order statistics, Acta Mathematica Academiae Scientiarum Hungarica 4, 191 (1953)

    work page 1953

  74. [75]

    Renner, Security of quantum key distribution, International Journal of Quantum Information 06, 1 (2008)

    R. Renner, Security of quantum key distribution, International Journal of Quantum Information 06, 1 (2008)

    work page 2008

  75. [76]

    Schuster, J

    T. Schuster, J. Haferkamp, and H.-Y. Huang, Random unitaries in extremely low depth, Science 389, 92 (2025)

    work page 2025

  76. [77]

    A. M. Krol and Z. Al-Ars, Beyond quantum Shannon decomposition: Circuit construction for n-qubit gates based on block-ZXZ decomposition, Phys. Rev. Appl. 22, 034019 (2024)

    work page 2024

  77. [78]

    S. A. Moses et al., A race-track trapped-ion quantum processor, Phys. Rev. X 13, 041052 (2023)

    work page 2023

  78. [79]

    Olmschenk et al., Manipulation and detection of a trapped yb + hyperfine qubit, Phys

    S. Olmschenk et al., Manipulation and detection of a trapped yb + hyperfine qubit, Phys. Rev. A 76, 052314 (2007)

    work page 2007

  79. [80]

    Sørensen and K

    A. Sørensen and K. Mølmer, Entanglement and quantum computation with ions in thermal motion, Phys. Rev. A 62, 022311 (2000)

    work page 2000

  80. [81]

    P. J. Lee et al., Phase control of trapped ion quantum gates, Journal of Optics B: Quantum and Semiclassical Optics 7, S371 (2005)

    work page 2005

Showing first 80 references.