Pith. sign in

REVIEW 2 major objections 4 minor 54 references

Resource quantification for programming low-depth quantum circuits

T0 review · 2 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Programming a low-depth brickwork quantum circuit on N qubits, with allowed error ~ 1/polylog N, requires Θ(N polylog N) qubits of program memory in the worst case.

desk verdict The upper bound is clean and the problem is well chosen, but the lower bound that gives the Θ(N polylog N) claim imports a lemma whose hypothesis is not met, so the tightness result is not established. read the letter →

arxiv 2509.09642 v2 pith:EISNVURP submitted 2025-09-11 quant-ph

Entong He , Yuxiang Yang This is my paper
classification quant-ph MSC 81P6881P45 PACS 03.67.-a03.67.Lx
keywords quantumprogrammingprogramcostlow-depthcircuitsbrickworkunitarydesignsHolevoinformationcoveringnumberNISQ
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

To run a quantum computation on a remote device, the user sends a quantum program state to a fixed processor; the number of qubits needed to store that state is the program cost. This paper asks how large that cost must be when the target is a low-depth brickwork circuit on N qubits rather than an arbitrary unitary, with the allowed error shrinking like 1/polylog N. It establishes a worst-case bound of Θ(N polylog N) qubits, matching lower and upper bounds for brickwork circuits. If correct, this is the first tight large-N characterization: NISQ-scale low-depth computations can be programmed with quasi-linear memory, and programming each small gate separately is essentially optimal. The paper also shows that generic universal programming schemes need poly(2^N,1/√ε) gates, making them impractical in this regime.

What carries the argument

The central object is the program cost, the base-2 logarithm of the dimension of the subspace spanned by the processor's program states. The lower-bound machinery is the measure-and-operate programming framework together with Holevo information: an approximate unitary n-design supplies a hard ensemble, and a continuity bound on von Neumann entropy forces any successful processor's program states to contain many bits. The upper-bound machinery is the covering number of the set of brickwork-circuit unitaries, with a postselected processor that stores the index of the closest net point. The light-cone argument—grouping local gates into larger blocks—is the tool used to test whether layout infor

What would settle it

Construct a family of N-qubit low-depth brickwork circuits and an explicit programming scheme with program dimension exp(o(N polylog N)) that achieves diamond-norm error O(1/polylog N) on every circuit in the family; this would refute the claimed Ω(N polylog N) lower bound. A narrower test is whether the imported lemma's bound ||P_U − (U⊗I)^{⊗n}||_⋄ ≤ 4n√(2ε) can fail when U is restricted to the brickwork family; if it fails, the lower-bound proof collapses.

Watch

Extended reading notes

Core claim

The paper's central claim is that the program cost cP = log2 dP of an N-qubit low-depth brickwork circuit obeys a tight worst-case bound cP = Θ(N polylog N) when the diamond-norm error is ε ~ 1/polylog N. The lower bound is information-theoretic: feeding states created by an approximate unitary n-design through any ε-universal processor forces the program states to carry Ω(n log(d/n)) bits of Holevo information, and optimizing n gives Ω(N polylog N). The upper bound is combinatorial: an ε-net of brickwork-circuit unitaries has size roughly [(eN/k)^k (12ℓ/ε)^{2^{2k+1}}]^ℓ, so storing the index of the nearest net point costs O(N polylog N) qubits. The paper further claims that generic universa

Load-bearing premise

The lower bound assumes that a lemma proved for processors approximating every unitary in U(d) still holds for a processor required only to program low-depth circuits; the paper does not justify that the diamond-norm closeness to U^{⊗n} survives this restriction, and it also uses a cited low-depth unitary-design construction without re-proving it at the needed parameters.

Editorial extensions

If this is right

  • The worst-case program cost for low-depth brickwork circuits is exactly Θ(N polylog N) at error ε ~ 1/polylog N; no asymptotically smaller memory scheme exists.
  • Generic universal programming of arbitrary N-qubit unitaries requires exponentially more memory and gates (poly(2^N, 1/√ε)), so restricting to low-depth circuits is essential for practical programmable NISQ processors.
  • Programming each constant-size local gate separately achieves the optimal scaling; light-cone reduction does not improve the asymptotic cost for generic local gates.
  • As the allowed error ε goes to 0, the program cost diverges whenever √ε 2^N > 1, recovering the no-programming theorem in the exact limit.
  • Programming and learning separate for low-depth circuits: some low-depth brickwork unitaries are hard to learn but can be programmed efficiently.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: The lower-bound proof imports a lemma proven for processors that are ε-universal over all of U(d) into the restricted low-depth setting; if that lemma cannot be re-proven under restricted universality, the Ω(N polylog N) worst-case bound may be unsupported even though the upper bound is concrete.
  • Editorial inference: The upper-bound construction assumes the sender knows a classical description of the target circuit (to pick the nearest net point), so this is a model of programming a known circuit, not learning an unknown one; the tight cost can be read as the storage price of that description.
  • Editorial inference: The same Holevo-information and covering-number techniques should extend to other constant-degree circuit families and to 2D brickwork layouts; a testable prediction is that Θ(N polylog N) persists, with the polylog exponent set by allowed depth and geometry.
  • Editorial inference: The commuting-Pauli example suggests a broader criterion—light-cone reduction saves memory when the effective parameter count per light-cone grows more slowly than the number of local gates it contains; other structured families satisfying this criterion may yield further savings.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. This paper studies the resources required to approximately program low-depth brickwork quantum circuits on N qubits. The main formal result claims a tight worst-case program cost Θ(N polylog N) when the programming error is ε ∼ 1/polylog N: Theorem 18 gives an Ω(N polylog N) lower bound based on Holevo information of approximate unitary designs supported on low-depth circuits, and Theorem 23 gives a matching O(N polylog N) upper bound via a covering-net construction. The paper also analyzes the gate complexity of the measure-and-operate programming scheme and discusses a light-cone reduction trade-off.

Significance. If the lower bound were established for processors restricted to the low-depth family, the tight Θ(N polylog N) characterization would be a meaningful advance over prior program-cost bounds, which are non-trivial only for constant N. The upper bound is simple and robust. The lower-bound strategy—comparing the Holevo information of program states for an approximate design with the Haar ensemble—is conceptually appealing and could be of independent interest. However, the proof currently imports a lemma whose hypothesis is not satisfied by the restricted processors appearing in the main claim.

major comments (2)
  1. [Theorem 18 / Lemma 14] The lower bound applies Lemma 14, stated for an ε-universal processor over all U(d), to a processor only required to program low-depth brickwork circuits. The design νκ is supported inside the low-depth family (Definition 7), which is not a group and is not closed under the twirls used in [16, Appendix A] to prove Lemma 14. Consequently the bound ||P_V-(V⊗I)^{⊗n}||⋄ ≤ 4n√(2ε) is not justified for each V in the support, and the chain (4)-(6) that transfers Holevo information from the ideal ensemble to the program states breaks at its first step. Since Theorem 23 constructs only a restricted processor, the claimed Θ(N polylog N) tightness is not established. Please either prove a restricted version of Lemma 14 with a V-independent K_C, supply an alternative lower bound, or clearly restrict Theorem 18 to full-U(d) universal processors (which would not match the upper bound). This is load-be
  2. [Theorem 18, proof] The proof assumes, citing [40], a diamond-norm κ-approximate n-design supported on 1D low-depth brickwork circuits with depth O(polylog N) for n=O(polylog N) and κ=Ω(2^{-polylog N}). The depth bound in Table 1 depends on a parameter ξ with t=O(2^{2ξ/5}); the authors should verify that the required range is covered by [40] and state the imported theorem precisely. This is not a criticism of [40] but a missing support in the present derivation.
minor comments (4)
  1. [Theorem 18, statement] The displayed lower bound contains the factor (1−ϖ/(4√(2ε))−1), which is negative for all allowed ϖ. From the proof, the intended factor is presumably ((1−ϖ)/(4√(2ε))−1); please correct.
  2. [Section 4, program dimension] d_P is defined as dim span{ψ_{P,U}|U∈U(d)}. For restricted processors the span should be over the programmed family U_{k,ℓ,D}; otherwise the Holevo bound χ(...)≤log d_P is vacuous if the processor is not defined outside the family.
  3. [Example 25] The claim [∏_{j=1}^k P_{q_j}, ∏_{j=1}^k P_{q'_j}]=0 for any q,q' is false when supports overlap and the Pauli types differ (e.g., X and Z on the same qubit anticommute). The light-cone simplification in the example relies on commutativity; as stated, the example is invalid.
  4. [Theorem 1 (informal)] The theorem calls the scheme 'optimal universal programming' but the section only proves an upper bound on gate complexity; the word 'optimal' is potentially misleading.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central lower and upper bounds are independent derivations, and cited results are external evidence rather than inputs disguised as predictions.

full rationale

I walked the claimed derivation chain. The central lower bound (Theorem 18) is an information-theoretic argument: it uses Schur–Weyl dimension counting, Holevo information, and the Alicki–Fannes–Winter bound, and it imports Lemma 14 from [16] as a black box. Although [16] shares an author, Lemma 14 is a separately published, parameter-free statement about ε-universal processors over all of U(d); the present paper does not define any quantity in terms of the target program cost c_P, and the lemma does not include the low-depth result as an assumption. The upper bound (Theorem 23) is a clean covering-net counting argument with an explicit postselection processor construction (Eq. 9); again no parameter is fitted and no conclusion is assumed. Theorem 1 and the light-cone discussion restate or extend known complexity facts, not rename the target result. The most delicate point is that Theorem 18 applies Lemma 14 to a processor that may only need to program low-depth brickwork circuits, even though Lemma 14 is stated for full U(d) universality. That is a real hypothesis-mismatch / correctness risk: if the lemma requires full-group universality, the Ω(N polylog N) lower bound would not follow from the given proof. But this is not circularity, because nothing forces ||P_V − (V⊗I)^{⊗n}||⋄ ≤ 4n√(2ε) by definition of the restricted low-depth program family. Similarly, the use of the [40] unitary-design construction as a low-depth brickwork circuit is a cited external construction, not an assumption equivalent to the conclusion. The self-reference to [25] in Remark 19 is a comparison ("improves the bound"), not a load-bearing input. Therefore no circular step is present; the score is 0. If Lemma 14's hypotheses are not satisfied, the lower bound would be unproven, but that would be an open technical correctness issue, not circular derivation.

Assumptions & free parameters 2 free parameters · 7 assumptions · 0 invented entities

The central lower and upper bounds rest on standard tools (Schur-Weyl, entropy continuity, covering numbers) plus two external constructions (Yang-Renner-Chiribella programming lemma and Schuster-Haferkamp-Huang designs). No constants are fitted to data; ϖ and κ are tunable parameters whose values do not affect the asymptotic scaling.

free parameters (2)
  • ϖ
    Constant chosen in Theorem 18 within (0,1-4√(2ε)) to make a prefactor positive; asymptotically can be fixed and does not affect the Θ scaling.
  • κ
    Error of the approximate unitary design used in the lower bound; constrained to κ=Ω(2^{-polylog N})<1, chosen small so the prefactor stays positive.
assumptions (7)
  • standard math Schur-Weyl duality (Lemma 6) holds for tensor powers of U(d).
    Invoked to decompose H^⊗n and to identify the dimension d_n in the Holevo lower bound.
  • domain assumption Lemma 14 from [16]: for an ε-universal processor over U(d), channels P_U exist with ||P_U-(U⊗I)^⊗n||⋄≤4n√(2ε).
    External theorem by one of the present authors; used pointwise for U in the design ensemble, though the cited lemma is stated for full-group universality.
  • domain assumption Polylog-depth approximate unitary t-designs with t=O(polylog N) exist on N qubits (Schuster, Haferkamp, Huang [40]).
    Loaded-bearing for the lower bound: the random unitaries used to build the state ensemble must themselves be low-depth circuits.
  • standard math Alicki-Fannes-Winter entropy continuity bound (Lemma 16).
    Used to convert trace-distance closeness of channels into entropy differences in the Holevo argument.
  • standard math Dimension identity d_n = binom(n+d^2-1, d^2-1) and the lower-bound inequality in Lemma 17.
    Combinatorial identity used to evaluate the entropy lower bound in Theorem 18.
  • domain assumption Covering number bound for U(d) (Lemma 21 from [23]).
    External result used in the upper-bound counting argument for the program cost.
  • domain assumption Error propagation across a brickwork circuit: ℓ gates each ε-close give total error ℓε (Lemma 13).
    Used for gate-wise programming and for the covering-net construction in Lemma 22.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Resource quantification for programming low-depth quantum circuits." pith.science (2026). https://pith.science/paper/EISNVURP

@misc{pith2026250909642,
  author       = {Pith},
  title        = {Pith review of: Resource quantification for programming low-depth quantum circuits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EISNVURP}},
  note         = {Machine review of arXiv:2509.09642}
}
abstract

Noisy intermediate-scale quantum (NISQ) devices pave the way for implementing quantum algorithms that offer quantum advantages over their classical counterparts. Due to the intrinsic noise and decoherence in the physical system, NISQ machines are naturally modeled as large-scale, low-depth quantum circuits. In practice, executing such circuits requires sending program states that encode the relevant instructions to a programmable quantum computer, typically through a cloud service. Existing programming approaches designed for generic unitary transformations are computationally inefficient in the low-depth setting, and therefore remain unsatisfactory. As such, to realize NISQ algorithms, it is crucial to find an efficient way to program low-depth circuits as the number of qubits $N$ increases. Here, we investigate the circuit complexity and the size of quantum memory, known as the program cost, required to program low-depth brickwork circuits. We establish a tight worst-case program cost of $\Theta(N \mathrm{polylog} N)$ for universally programming low-depth brickwork circuits in the large-$N$ regime. Moreover, we analyze the trade-off between the cost of describing the layout of local gates and the cost of programming them to implement the target unitaries via the light-cone argument. Our findings suggest that faithful gate-wise programming is essentially optimal in the low-depth regime.

Figures

Figures reproduced from arXiv: 2509.09642 by the authors.

Figure 1
Figure 1. Illustration of a 1D 2-local brickwork quantum circuit consisting of [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. The MO universal programming scheme. post-selection with a continuous measurement on |ψP,U ⟩, namely the measure-and-operate operation. A diagrammatic illustration is shown in [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Examples of light-cone reduction of 1D and 2D 2-local brickwork circuits. [PITH_FULL_IMAGE:figures/full_fig_p017_3.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

54 extracted references · 4 linked inside Pith

  1. [16]

    Optimal universal program- ming of unitary gates

    Yuxiang Yang, Renato Renner, and Giulio Chiribella. “Optimal universal program- ming of unitary gates”. Phys. Rev. Lett.125, 210501 (2020)

    2020

  2. [40]

    Random unitaries in extremely low depth

    Thomas Schuster, Jonas Haferkamp, and Hsin-Yuan Huang. “Random unitaries in extremely low depth”. Science389, 92–96 (2025)

    2025

  3. [1]

    Quantum Computing in the NISQ era and beyond

    John Preskill. “Quantum Computing in the NISQ era and beyond”. Quantum2, 79 (2018)

    2018

  4. [2]

    A fast quantum mechanical algorithm for database search

    Lov K. Grover. “A fast quantum mechanical algorithm for database search”. In Pro- ceedingsofthe28thAnnualACMSymposiumonTheoryofComputing. Page212–219. STOC ’96New York, NY, USA (1996). Association for Computing Machinery

    1996

  5. [3]

    Polynomial-time algorithms for prime factorization and discrete loga- rithms on a quantum computer

    Peter W. Shor. “Polynomial-time algorithms for prime factorization and discrete loga- rithms on a quantum computer”. SIAM Journal on Computing26, 1484–1509 (1997)

    1997

  6. [4]

    Quantum algorithm for linear systems of equations

    Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. “Quantum algorithm for linear systems of equations”. Phys. Rev. Lett.103, 150502 (2009). 20

    2009

  7. [5]

    Noisy intermediate-scale quantum algorithms

    Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik. “Noisy intermediate-scale quantum algorithms”. Rev. Mod. Phys.94, 015004 (2022)

    2022

  8. [6]

    Shallowquantumcircuits: Algorithms, complexity, andfaulttolerance

    YunchaoLiu. “Shallowquantumcircuits: Algorithms, complexity, andfaulttolerance”. PhD thesis. University of California, Berkeley. (2024)

    2024

Show all 54 references
  1. [7]

    Quantum advantage with shallow circuits

    Sergey Bravyi, David Gosset, and Robert König. “Quantum advantage with shallow circuits”. Science362, 308–311 (2018)

    2018

  2. [8]

    Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

    Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal. “Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits”. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Page 515–526. STOC 2019New...

    2019

  3. [9]

    Delegating private quantum computations

    Anne Broadbent. “Delegating private quantum computations”. Canadian Journal of Physics93, 941–946 (2015)

    2015

  4. [10]

    A one-query lower bound for unitary synthesis and breaking quantum cryptography

    Alex Lombardi, Fermi Ma, and John Wright. “A one-query lower bound for unitary synthesis and breaking quantum cryptography”. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Page 979–990. STOC 2024New York, NY, USA (2024). Association for Computing Machinery

    2024

  5. [11]

    Programmable quantum gate arrays

    M. A. Nielsen and Isaac L. Chuang. “Programmable quantum gate arrays”. Physical Review Letters79, 321–324 (1997)

    1997

  6. [12]

    Probabilistic implementation of universal quantum processors

    Mark Hillery, Vladimír Bužek, and Mário Ziman. “Probabilistic implementation of universal quantum processors”. Phys. Rev. A65, 022301 (2002)

    2002

  7. [13]

    Measurement-based quantum computation beyond the one-way model

    D. Gross, J. Eisert, N. Schuch, and D. Perez-Garcia. “Measurement-based quantum computation beyond the one-way model”. Phys. Rev. A76, 052315 (2007)

    2007

  8. [14]

    Asymptotic teleportation scheme as a uni- versal programmable quantum processor

    Satoshi Ishizaka and Tohya Hiroshima. “Asymptotic teleportation scheme as a uni- versal programmable quantum processor”. Phys. Rev. Lett.101, 240501 (2008)

    2008

  9. [15]

    Resource quan- tification for the no-programing theorem

    Aleksander M. Kubicki, Carlos Palazuelos, and David Pérez-García. “Resource quan- tification for the no-programing theorem”. Physical Review Letters122(2019)

    2019

  10. [17]

    Programmability of covariant quantum channels

    Martina Gschwendtner, Andreas Bluhm, and Andreas Winter. “Programmability of covariant quantum channels”. Quantum5, 488 (2021)

    2021

  11. [18]

    Port-Based State Preparation and Appli- cations

    Garazi Muguruza and Florian Speelman. “Port-Based State Preparation and Appli- cations”. Quantum8, 1573 (2024)

    2024

  12. [19]

    Quantum advantage in storage and retrieval of isometry channels

    Satoshi Yoshida, Jisho Miyazaki, and Mio Murao. “Quantum advantage in storage and retrieval of isometry channels” (2025). arXiv:2507.10784

    2025 arXiv

  13. [20]

    Computational complexity: A modern approach

    Sanjeev Arora and Boaz Barak. “Computational complexity: A modern approach”. Cambridge University Press. (2009)

    2009

  14. [21]

    Linear growth of quantum circuit complexity

    Jonas Haferkamp, Philippe Faist, Naga B. T. Kothakonda, Jens Eisert, and Nicole Yunger Halpern. “Linear growth of quantum circuit complexity”. Nature Physics18, 528–532 (2022). 21

    2022

  15. [22]

    Approximatet-designs in generic circuit architectures

    Daniel Belkin, James Allen, Soumik Ghosh, Christopher Kang, Sophia Lin, James Sud, Frederic T. Chong, Bill Fefferman, and Bryan K. Clark. “Approximatet-designs in generic circuit architectures”. PRX Quantum5, 040344 (2024)

    2024

  16. [23]

    Learning quantum states and unitaries of bounded gate complex- ity

    Haimeng Zhao, Laura Lewis, Ishaan Kannan, Yihui Quek, Hsin-Yuan Huang, and Matthias C. Caro. “Learning quantum states and unitaries of bounded gate complex- ity”. PRX Quantum5(2024)

    2024

  17. [24]

    Learning shallow quantum circuits

    Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, and Jarrod R. McClean. “Learning shallow quantum circuits”. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Page 1343–1351. STOC 2024New York, NY, USA (2024). Associa...

    2024

  18. [25]

    Compression of quantum shallow-circuit states

    Yuxiang Yang. “Compression of quantum shallow-circuit states”. Phys. Rev. Lett.134(2025)

    2025

  19. [26]

    Quantum computation and quantum infor- mation: 10th anniversary edition

    Michael A. Nielsen and Isaac L. Chuang. “Quantum computation and quantum infor- mation: 10th anniversary edition”. Cambridge University Press. (2012)

    2012

  20. [27]

    On the pauli spectrum ofQAC0

    Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, and Henry Yuen. “On the pauli spectrum ofQAC0”. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Page 1498–1506. STOC ’24. ACM (2024)

    2024

  21. [28]

    Symmetry, representations, and invariants

    Roe Goodman and Nolan R. Wallach. “Symmetry, representations, and invariants”. Springer New York. (2009)

    2009

  22. [29]

    Applications of coherent classical communication and the schur transform to quantum information theory

    Aram W. Harrow. “Applications of coherent classical communication and the schur transform to quantum information theory”. PhD thesis. Massachusetts Institute of Technology. (2005)

    2005

  23. [30]

    Simple Con- structions of Linear-Depth t-Designs and Pseudorandom Unitaries

    Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen. “ Simple Con- structions of Linear-Depth t-Designs and Pseudorandom Unitaries ”. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). Pages 485–

    2024

  24. [31]

    Exact and approximate unitary 2-designs and their application to fidelity estimation

    Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. “Exact and approximate unitary 2-designs and their application to fidelity estimation”. Phys. Rev. A80, 012304 (2009)

    2009

  25. [32]

    Optimal quantum learning of a unitary transformation

    Alessandro Bisio, Giulio Chiribella, Giacomo Mauro D’Ariano, Stefano Facchini, and Paolo Perinotti. “Optimal quantum learning of a unitary transformation”. Phys. Rev. A81, 032324 (2010)

    2010

  26. [33]

    Scalable noise estimation with random unitary operators

    Joseph Emerson, Robert Alicki, and Karol Zyczkowski. “Scalable noise estimation with random unitary operators”. Journal of Optics B: Quantum and Semiclassical Optics7, S347–S352 (2005)

    2005

  27. [34]

    Creating superpositions that correspond to efficiently integrable probability distributions

    Lov Grover and Terry Rudolph. “Creating superpositions that correspond to efficiently integrable probability distributions” (2002). arXiv:quant-ph/0208112

    2002 arXiv

  28. [35]

    An efficient high dimensional quantum Schur transform

    Hari Krovi. “An efficient high dimensional quantum Schur transform”. Quantum3, 122 (2019)

    2019

  29. [36]

    Quantum state preparation with optimal circuit depth: Implementations and applications

    Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. “Quantum state preparation with optimal circuit depth: Implementations and applications”. Phys. Rev. Lett.129, 230504 (2022)

    2022

  30. [37]

    Approximate unitary t-designs by short ran- dom quantum circuits using nearest-neighbor and long-range gates

    Aram W. Harrow and Saeed Mehraban. “Approximate unitary t-designs by short ran- dom quantum circuits using nearest-neighbor and long-range gates”. Communications in Mathematical Physics401, 1531–1626 (2023). 22

    2023

  31. [38]

    Efficient approximate unitary designs from random pauli rotations

    Jeongwan Haah, Yunchao Liu, and Xinyu Tan. “Efficient approximate unitary designs from random pauli rotations”. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). Pages 463–475. (2024)

    2024

  32. [39]

    Incompressibility and spectral gaps of random circuits

    Chi-Fang Chen, Jeongwan Haah, Jonas Haferkamp, Yunchao Liu, Tony Metger, and Xinyu Tan. “Incompressibility and spectral gaps of random circuits” (2024). arXiv:2406.07478

    2024 arXiv

  33. [41]

    Optimal estimation of group transformations using entanglement

    G. Chiribella, G. M. D’Ariano, and M. F. Sacchi. “Optimal estimation of group transformations using entanglement”. Phys. Rev. A72, 042338 (2005)

    2005

  34. [42]

    Query-optimal estimation of unitary channels in diamond distance

    Jeongwan Haah, Robin Kothari, Ryan O’Donnell, and Ewin Tang. “Query-optimal estimation of unitary channels in diamond distance”. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). Pages 363–390. (2023)

    2023

  35. [43]

    Synthesis of quantum logic circuits

    Vivek V. Shende, Stephen S. Bullock, and Igor L. Markov. “Synthesis of quantum logic circuits”. In Proceedings of the 2005 Asia and South Pacific Design Automation Conference. Page 272–275. ASP-DAC ’05New York, NY, USA (2005). Association for Computing Machinery

    2005

  36. [44]

    Classical and quantum computation

    Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. “Classical and quantum computation”. Number 47 in Graduate Studies in Mathematics. American Mathemat- ical Soc. (2002)

    2002

  37. [45]

    Bounds for the quantity of information transmitted by a quantum communication channel

    Alexander Semenovich Holevo. “Bounds for the quantity of information transmitted by a quantum communication channel”. Problemy Peredachi Informatsii9, 3–11 (1973). url:https://www.mathnet.ru/eng/ppi903

    1973

  38. [46]

    Tight uniform continuity bounds for quantum entropies: Condi- tional entropy, relative entropy distance and energy constraints

    Andreas Winter. “Tight uniform continuity bounds for quantum entropies: Condi- tional entropy, relative entropy distance and energy constraints”. Communications in Mathematical Physics347, 291–313 (2016)

    2016

  39. [47]

    Asymptotic values for degrees associated with strips of young dia- grams

    Amitai Regev. “Asymptotic values for degrees associated with strips of young dia- grams”. Advances in Mathematics41, 115–136 (1981)

    1981

  40. [48]

    Optimal compression for identically prepared qubit states

    Yuxiang Yang, Giulio Chiribella, and Masahito Hayashi. “Optimal compression for identically prepared qubit states”. Phys. Rev. Lett.117, 090502 (2016)

    2016

  41. [49]

    On the computa- tional power ofQAC 0 with barely superlinear ancillae

    Anurag Anshu, Yangjing Dong, Fengning Ou, and Penghui Yao. “On the computa- tional power ofQAC 0 with barely superlinear ancillae”. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing. Page 1476–1487. STOC ’25New York, NY, USA (2025). Association for Computi...

    2025

  42. [50]

    Operator lipschitz functions (english trans- lation)

    Alexei Aleksandrov and Vladimir Peller. “Operator lipschitz functions (english trans- lation)” (2016). arXiv:1611.01593

    2016 arXiv

  43. [51]

    Quantum state and unitary learn- ing implies circuit lower bounds

    Nai-Hui Chia, Daniel Liang, and Fang Song. “Quantum state and unitary learn- ing implies circuit lower bounds”. In Nika Haghtalab and Ankur Moitra, edi- tors, Proceedings of Thirty Eighth Conference on Learning Theory. Volume 291 of Proceedings of Machine Learning Research, pa...

    2025

  44. [52]

    On the geometry of stabi- lizer states

    Héctor J. García, Igor L. Markov, and Andrew W. Cross. “On the geometry of stabi- lizer states”. Quantum Info. Comput.14, 683–720 (2014)

    2014

  45. [53]

    Restrictions on realizable unitary operations imposed by symmetry and locality

    Iman Marvian. “Restrictions on realizable unitary operations imposed by symmetry and locality”. Nature Physics18, 283–289 (2022). 23

    2022

  46. [492]

    IEEE Computer Society

    Los Alamitos, CA, USA (2024). IEEE Computer Society

    2024

Pith tools

Reviewed August 4, 2026 · model on record in the stance chip above.