Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

An unconditional distribution learning advantage with shallow quantum circuits

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read The paper proves that shallow quantum circuits, but not shallow classical circuits, can exactly learn a distribution class.

desk verdict Solid separation result with one patchable proof gap in the classical hardness step. read the letter →

arxiv 2411.15548 v2 pith:RDZ2QDZI submitted 2024-11-23 quant-ph cs.AI

N. Pirnay , S. Jerbi , J.-P. Seifert , J. Eisert This is my paper · ORCID
classification quant-phcs.AI MSC 81P6868Q32 PACS 03.67.-a
keywords PACdistributionlearningQNC^0NC^0quantumadvantageshallowcircuitspoorman'sGHZstatetotalvariationdistancehyperplane
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

Constant-depth quantum circuits can solve a distribution-learning task that equally shallow classical circuits cannot. The task is to PAC-learn, from random samples, one of the distributions in a class produced by a fixed shallow quantum circuit, with the learner forced to output a shallow generator. The paper proves that a learner using QNC$^0$ generators recovers the target distribution exactly, while every learner using NC$^0$ generators must leave a total variation error of at least $1/\pi - O(1/\log n)$. This is an unconditional separation, built on a prior sampling hardness result rather than on cryptographic or unproven complexity assumptions. If correct, it shows that non-local correlations preparable in constant depth can already yield a provable learning advantage for near-term quantum circuits.

What carries the argument

The load-bearing object is the shift-parameterized distribution $(Z, \operatorname{pmmajmod}_{p,s}(Z))$ built on the binary-tree poor-man's GHZ state $|PM_n\rangle$, together with the cosine identity that carries the learning signal. The state $|PM_n\rangle$ is preparable in constant depth, and the circuit in Fig. 2a applies blocks of constant-size unitaries $U_{m,\theta}$ that approximate a non-unitary gate $A_{m,\theta}$; after measuring all but the last qubit, the last-qubit outcome has probability approximately $\cos^2(-\pi/4 + (\pi/p)(k+s))$, with $k = \sum_i x_i(-1)^{h(d)_i} \bmod p$. This one-dimensional profile is what makes the hidden shift $s$ learnable: the crossing at $1/2$ occurs exactly at $k = p-s$. The classical hardness side is carried by locality: every NC$^0$ generator is a local function, and a sub-tree partitioning argument inherited from distributional complexity forces local functions to stay far from the $\operatorname{pmmajmod}$ distributions.

What would settle it

Simulate the learning problem at small sizes: for a fixed nonzero $s \in \mathbb{F}_p$ and for increasing $N = 2n-2$ with $p \sim n^{\alpha}$, compute the minimum total variation distance between $(Z, \operatorname{pmmajmod}_{p,s}(Z))$ and every $(\epsilon \log N)^{1/2}$-local function, i.e. every NC$^0$ generator. If any such minimum falls below $1/2 - \omega(1/\log N)$ for some nonzero $s$, the uniform generalization used in the proof is false and Theorem IV.1 needs repair. In the same simulation, the predicted gap of $1/\pi - O(1/\log n)$ between the learned QNC$^0$ generator and any NC$^0$ generator should be directly observable.

Watch

Extended reading notes

Core claim

The paper's central claim is that the distribution class $\mathcal{D}$, whose elements are the Born distributions of a specific constant-depth quantum circuit family indexed by a hidden hyperplane shift $s \in \mathbb{F}_p$, is PAC-generator-learnable with zero error by QNC$^0$ but not by NC$^0$. Each $D_{n,p,s}$ is the output of a circuit that approximates the pair $(Z, \operatorname{pmmajmod}_{p,s}(Z))$: the 'poor man's majority mod $p$' function evaluated on a balanced binary tree, with a shift $s$. A quantum learner estimates the cosine profile $\cos^2(-\pi/4 + (\pi/p)(k+s))$ at $p$ values, identifies the unique crossing $k = p-s$, recovers $s$, and outputs the exact generating circuit, so the learned generator has total variation distance zero from the target. A classical constant-depth generator is a local function, and the known hardness result says that any such local function is at total variation distance at least $1/2 - O(1/\log N)$ from the ideal distribution, whereas the quantum circuit's own approximation error to that ideal distribution is at most $1/2 - 1/\pi + O(n^{-c})$. Combining the two gaps yields the quantitative separation $1/\pi - O(1/\log n)$.

Load-bearing premise

The argument needs the quoted classical-hardness theorem to hold uniformly for every hidden shift $s \in \mathbb{F}_p$, but the theorem is stated and proved only for $s=0$; the paper's assertion that the generalization is straightforward is not itself proved, so the full-class separation depends on that unproved extension.

Editorial extensions

If this is right

  • A PAC distribution-learning separation between QNC$^0$ and NC$^0$ holds unconditionally, with the quantum learner achieving exactly zero total variation error and every classical constant-depth learner incurring error at least $1/\pi - o(1)$.
  • The separation is an approximation-expressiveness gap rather than a sample-complexity gap: the quantum learner uses polynomially many examples, and giving the classical learner unlimited samples does not close the gap, since the lower bound applies to all local output functions.
  • Non-local correlations preparable by constant-depth circuits, here the binary-tree poor-man's GHZ correlations, are sufficient to power a learning advantage and not merely a sampling advantage.
  • For the distribution class $\mathcal{D}$, the hidden hyperplane parameter $s$ has polynomial description size, so the separation lives in the standard PAC setting where the concept class is polynomial in size.
  • The result indicates that constant-depth quantum devices can provably outperform classical shallow circuits on at least one generative learning task before noise-limited depth bounds set in.

Reading between the lines

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

  • Read as a reduction, the proof suggests a general pattern: any shallow-circuit sampling separation in which the target family is parameterized by an efficiently searchable label can be lifted to a PAC distribution-learning separation; the hyperplane shift $s$ is one instance of such a label, but the same template may work for other finite-field or group parameters.
  • The specific constant $1/\pi$ comes from the approximation constant in the sampling construction; the structural separation would survive with any constants as long as the quantum approximation error stays strictly below $1/2$ and the classical lower bound stays strictly above $1/2$.
  • A direct numerical check for small $n,p,s$ is within reach: simulate the circuit's Born distribution, run the cosine-estimation learner, and compute empirical TV distances for all local candidate functions; the predicted gap should be visible for modest $n$ if the uniform-in-$s$ generalization of the hardness theorem is valid.
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

3 major / 5 minor

Summary. The paper proves an unconditional PAC distribution learning separation between constant-depth quantum circuits (QNC^0) and constant-depth bounded fan-in classical circuits (NC^0). The authors define a distribution class D consisting of the Born distributions of a family of constant-depth quantum circuits, parameterized by a hyperplane shift s in a finite field F_p. They give a quantum learning algorithm that, from polynomially many samples, recovers s exactly with high probability and then outputs a constant-depth quantum generator whose output distribution equals the target distribution (TV distance 0). For the classical side, they invoke a hardness result of Watts and Parham to argue that no local (in particular, constant-depth) classical generator can approximate the target distributions below a constant TV error, yielding a gap of at least 1/π - O(1/log n). The main result is Theorem IV.1.

Significance. If the result holds as stated, this is a valuable addition to the quantum machine learning literature: it lifts an unconditional sampling separation into a genuine distribution learning separation with an explicit, sample-efficient quantum learner and a rigorous classical lower bound. The construction is concrete and builds on established work by Bene Watts and Parham, so the separation is unconditional rather than based on cryptographic assumptions. The paper is also honest about its limitations, noting that the data are highly structured and that the practical relevance is indirect. The proof structure is mostly transparent, and the main technical ideas are clearly exposed.

major comments (3)
  1. [III.D, Theorem 7, and Theorem IV.1 proof] Theorem 7 is stated and instantiated only for s = 0, but the proof of Theorem IV.1 applies the lower bound of Eq. (14) to an arbitrary s in the triangle inequality that yields the final gap. The text in Section III.D asserts that generalizing the hardness proofs of Ref. [17] to arbitrary shifts is straightforward, yet no proof or citation is supplied for this uniform statement. This is a load-bearing gap: as written, the classical hardness for every D_{n,p,s} in the class D is not established. The separation can likely be repaired by observing that D_{n,p,0} is already in D, so the lower bound for s = 0 suffices to show that NC^0 fails on the class D while QNC^0 succeeds on all of D; however, the theorem statement and proof should be adjusted accordingly, or the missing generalization should be proved.
  2. [Appendix B, Eq. (B4) and Eq. (B6)] The random vector v defined in Eq. (B4) is a sum over M examples of indicator vectors, with no normalization and no multiplicative factor p. However, the expectation in Eq. (B6) contains an unexplained factor p, and the subsequent application of the multivariate mean estimator (Lemma 13) to E[v] is dimensionally inconsistent with v as a sum of M terms. The derivation of the sample complexity M = O(p^4 log(p/δ)) in Eq. (B14) appears to rely on a per-sample vector with entries of magnitude at most p. The authors should redefine v consistently as a per-sample (or p-scaled and normalized) vector, and then verify that Lemma 13 with B = p yields the claimed bound. As written, the quantum learning proof in the appendix is not internally consistent.
  3. [III.B, Eq. (10), and Theorem IV.1] The distribution class D is defined in Eq. (10) without any restriction on the prime p, but the quantum learning result in Theorem III.1 (and its proof in Appendix B) only applies for p ∈ O(n^{1/3}). Consequently, Theorem IV.1, as stated for the entire class D, is not supported by the proof: for p growing faster than n^{1/3}, the claimed sample-efficient quantum learner is not established. The authors should either restrict the definition of D to the parameter range used in the proof, or explicitly state the main theorem for the subfamily of D with p in that range. Since the classical hardness requires p = Θ(N^α) with α < 1/3, restricting the class is natural and does not weaken the separation.
minor comments (5)
  1. [III.B] The first sentence of Section III.B contains a typo: 'Fist' should be 'First'.
  2. [Appendix B, Algorithm step 1] In the displayed algorithm, the normalization is written as '1/m' but the sample count is denoted M elsewhere; this should be '1/M' for consistency.
  3. [Fig. 2 caption] The caption refers to 'n vertex qubits', whereas |PM_n⟩ as defined in Eq. (6) has n−1 edge and n−1 vertex qubits; the notation in the figure should be reconciled with the main text.
  4. [Theorem IV.1 proof] The proof uses two distinct constants c, one from Theorem 5 with c ∈ (0,1/2) and one stated as c ∈ (0,1/3); the relationship between these constants should be clarified, and the asymptotic notation should be made uniform.
  5. [Appendix B, Lemma 14 proof] The derivative check is performed on the interval [0,1/2], but the statement only needs x ∈ [0,1/3]; the argument is valid but the interval should be aligned with the claim.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the learning separation rests on external sampling hardness results and a genuine parameter-estimation algorithm; the s=0-to-all-s gap is a correctness concern, not circularity.

full rationale

The paper's central claim is not circular. The target distribution class D is defined as the Born distributions of a fixed constant-depth quantum circuit family parameterized by an unknown hyperplane shift s. The quantum learner must infer s from samples and then output the known circuit with that s; the sample-complexity argument (Appendix B) is a genuine parameter-estimation proof using a mean-estimation lemma and a cosine-crossing identification. The classical lower bound is imported from the external Watts–Parham result (Ref. [17]) and Viola's distribution-complexity machinery, not from the authors' own prior work. No fitted parameter is renamed as a prediction, and no uniqueness theorem or ansatz is smuggled in via self-citation. The only notable weakness is that Theorem 7 is stated and proved only for s=0, while the proof of Theorem IV.1 applies Eq. (14) to an arbitrary shift s; the text asserts without proof that the generalization is straightforward. That is a correctness gap in the uniform statement of Theorem IV.1, not a reduction of the result to its own inputs, and it does not raise the circularity score. The quantum-generation side is by construction part of the problem definition, but the learning task—recovering s from samples—is nontrivial and independently analyzed, so the derivation is self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on imported sampling hardness results from Watts and Parham (domain assumptions), a standard measure concentration bound from Viola, and an unproven generalization of the hardness to arbitrary hyperplane shifts. No free parameters are fitted to data; the constants in the algorithm are chosen for convenience.

assumptions (4)
  • domain assumption Theorems 3, 4, 5, and 7 of Watts and Parham [17] (sampling advantage of QNC0 over NC0 for the constructed distributions).
    The paper's separation is built directly on these theorems, which are cited and not reproven. In particular, Theorem 5 (approximation of the target distribution by a constant-depth quantum circuit) and Theorem 7 (classical hardness) are imported.
  • standard math Fact 11 (Viola [22]): for nonzero integers a_i and uniform bits x_i, the sum Sigma a_i x_i mod p is within TV distance sqrt(p) e^{-t/p^2} of uniform.
    Used in Appendix B to bound the marginals P_k of the poor-man's majority mod p sum, ensuring the learner can estimate cos^2 values.
  • ad hoc to paper The classical hardness lower bound for constant-depth circuits holds uniformly for every shift s in F_p, not only s=0.
    Theorem 7 in the paper is stated for s=0, but the main theorem (IV.1) needs the lower bound for arbitrary s. The text says the generalization is straightforward, but no proof is supplied.
  • domain assumption Definitions of QNC0 and NC0 as constant-depth circuits with one/two-qubit gates and bounded fan-in gates, respectively, and the PAC generator learning framework.
    These are standard models in quantum and classical complexity theory; the paper uses them without proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An unconditional distribution learning advantage with shallow quantum circuits." pith.science (2026). https://pith.science/paper/RDZ2QDZI

@misc{pith2026241115548,
  author       = {Pith},
  title        = {Pith review of: An unconditional distribution learning advantage with shallow quantum circuits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RDZ2QDZI}},
  note         = {Machine review of arXiv:2411.15548}
}
read the original abstract

One of the core challenges of research in quantum computing is concerned with the question whether quantum advantages can be found for near-term quantum circuits that have implications for practical applications. Motivated by this mindset, in this work, we prove an unconditional quantum advantage in the probably approximately correct (PAC) distribution learning framework with shallow quantum circuit hypotheses. We identify a meaningful generative distribution learning problem where constant-depth quantum circuits using one and two qubit gates (QNC^0) are superior compared to constant-depth bounded fan-in classical circuits (NC^0) as a choice for hypothesis classes. We hence prove a PAC distribution learning separation for shallow quantum circuits over shallow classical circuits. We do so by building on recent results by Bene Watts and Parham on unconditional quantum advantages for sampling tasks with shallow circuits, which we technically uplift to a hyperplane learning problem, identifying non-local correlations as the origin of the quantum advantage.

Figures

Figures reproduced from arXiv: 2411.15548 by the authors.

Figure 1
Figure 1. a) Constant depth quantum circuits with one- and two-qubit gates are compared with b) constant-depth bounded fan-in [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. a) Unitary circuit producing the target distribution [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Constant-depth non-unitary circuit producing an approximate distribution [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

  1. Hardness of Quantum Distribution Learning and Quantum Cryptography

    quant-ph 2025-07 conditional novelty 7.0 of 10

    One-way puzzles exist if and only if proper quantum distribution learning is average-case hard, and PP ≠ BQP if and only if agnostic quantum distribution learning with KL divergence is hard.

Reference graph

Works this paper leans on

40 extracted references · 33 canonical work pages · cited by 1 Pith paper

  1. [17]

    To be more precise, Ref

    introduce a class of distributions {Dn}, for which they show that, asymptotically in n, a constant-depth quantum circuit samples approximately from Dn with higher fidelity than any constant-depth classical circuit could. To be more precise, Ref. [17] proves the following theorem. Theorem 3 (Theorem 3 in Ref. [17]). For eachδ ∈ (0, 1), there exists a famil...

    work page

  2. [1]

    There exists a constant-depth quantum circuit which takes state vector |0n⟩ as input and produces a dis- tribution which has total variation distance at most 1 6 + O (n−c) from Dn for some c ∈ (0, 1)

    work page

  3. [2]

    edge” qubits of the state vector |PMn⟩. The lower box indicates the n “vertex

    Each classical circuit with fan-in 2 which takes n + nδ random bits as input and has total variation distance at most 1 2 − ω(1/ log n) from Dn has depth Ω(log logn). 3 Figure 2. a) Unitary circuit producing the target distribution Dn,p,s. The upper box indicates the n − 1 “edge” qubits of the state vector |PMn⟩. The lower box indicates the n “vertex” qub...

    work page

  4. [3]

    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)

    2019

  5. [4]

    P. W. Shor, Polynomial-time algorithms for prime factor- ization and discrete logarithms on a quantum computer, SIAM J. Comp. 26, 1484 (1997)

    work page 1997

  6. [5]

    Montanaro, Quantum algorithms: an overview, npj Quant

    A. Montanaro, Quantum algorithms: an overview, npj Quant. Inf. 2, 15023 (2016)

    work page 2016

  7. [6]

    Carleo, I

    G. Carleo, I. Cirac, K. Cranmer, L. Daudet, M. Schuld, N. Tishby, L. V ogt-Maranto, and L. Zdeborová, Machine learning and the physical sciences, Rev. Mod. Phys. 91, 045002 (2019)

    work page 2019

  8. [7]

    Hangleiter and J

    D. Hangleiter and J. Eisert, Computational advantage of quantum random sampling, Rev. Mod. Phys. 95, 035001 (2023). 7

    work page 2023

Show all 40 references
  1. [8]

    Biamonte, P

    J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Quantum machine learning, Na- ture 549, 195 (2017)

    2017

  2. [9]

    Sweke, J.-P

    R. Sweke, J.-P. Seifert, D. Hangleiter, and J. Eisert, On the quantum versus classical learnability of discrete distribu- tions, Quantum 5, 417 (2021)

    2021

  3. [10]

    Schuld and N

    M. Schuld and N. Killoran, Is quantum advantage the right goal for quantum machine learning?, PRX Quantum 3, 030101 (2022)

    2022

  4. [11]

    Gyurik and V

    C. Gyurik and V . Dunjko, On establishing learning sepa- rations between classical and quantum machine learning with classical data, (2022), arXiv:2208.06339

    2022 arXiv

  5. [12]

    Jerbi, C

    S. Jerbi, C. Gyurik, S. Marshall, H. Briegel, and V . Dunjko, Parametrized quantum policies for reinforcement learn- ing, Adv. Neur. Inf. Proc. Sys. (NeurIPS 2021)34, 28362 (2021)

    2021

  6. [13]

    Pirnay, R

    N. Pirnay, R. Sweke, J. Eisert, and J.-P. Seifert, A super- polynomial quantum-classical separation for density mod- elling, Phys. Rev. A 107, 042416 (2023)

    2023

  7. [14]

    Y . Liu, S. Arunachalam, and K. Temme, A rigorous and robust quantum speed-up in supervised machine learning, Nature Phys. 17, 1013 (2021)

    2021

  8. [15]

    Deshpande, P

    A. Deshpande, P. Niroula, O. Shtanko, A. V . Gorshkov, B. Fefferman, and M. J. Gullans, Tight bounds on the convergence of noisy random circuits to the uniform distri- bution, PRX Quantum 3, 040329 (2022)

    2022

  9. [16]

    Hinsche, M

    M. Hinsche, M. Ioannou, A. Nietner, J. Haferkamp, Y . Quek, D. Hangleiter, J.-P. Seifert, J. Eisert, and R. Sweke, A single T-gate makes distribution learning hard, Phys. Rev. Lett. 130, 240602 (2023)

    2023

  10. [18]

    Stilck Franca and R

    D. Stilck Franca and R. García-Patrón, Limitations of op- timization algorithms on noisy quantum devices, Nature Phys. 17, 1221 (2020)

    2020

  11. [19]

    Bravyi, D

    S. Bravyi, D. Gosset, and R. Koenig, Quantum advantage with shallow circuits, Science 362, 308 (2018)

    2018

  12. [20]

    A. B. Watts and N. Parham, Unconditional quantum advantage for sampling with shallow circuits, (2023), arXiv:2301.00995

    2023 arXiv

  13. [21]

    Arunachalam, A

    S. Arunachalam, A. B. Grilo, and A. Sundaram, Quantum hardness of learning shallow classical circuits, SIAM J. Comput. 50, 972 (2021)

    2021

  14. [22]

    A. B. Watts, R. Kothari, L. Schaeffer, and A. Tal, Expo- nential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits, inProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 (Association for Computing Mach...

    2019

  15. [23]

    Piroli, G

    L. Piroli, G. Styliaris, and J. I. Cirac, Quantum circuits assisted by local operations and classical communication: Transformations and phases of matter, Phys. Rev. Lett.127, 220503 (2021)

    2021

  16. [24]

    K. C. Smith, E. Crane, N. Wiebe, and S. Girvin, Deter- ministic constant-depth preparation of the AKLT state on a quantum processor using fusion measurements, PRX Quantum 4, 020315 (2023)

    2023

  17. [25]

    Viola, The complexity of distributions, SIAM J

    E. Viola, The complexity of distributions, SIAM J. Comp. 41, 191 (2012)

    2012

  18. [26]

    N. Ding, Y . Ren, and D. Gu, Pac learning depth-3 AC0 circuits of bounded top fanin, in Proceedings of the 28th International Conference on Algorithmic Learning Theory, Proceedings of Machine Learning Research, V ol. 76, edited by S. Hanneke and L. Reyzin (PMLR, 2017) pp. 667–680

    2017

  19. [27]

    Mossel, R

    E. Mossel, R. O’Donnell, and R. P. Servedio, Learning juntas, in Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing , STOC ’03 (Asso- ciation for Computing Machinery, New York, NY , USA,

  20. [28]

    J. Liu, M. Liu, J.-P. Liu, Z. Ye, Y . Wang, Y . Alexeev, J. Eisert, and L. Jiang, Towards provably efficient quan- tum algorithms for large-scale machine-learning models, Nature Comm. 15, 434 (2024)

    2024

  21. [29]

    Huang, Y

    H.-Y . Huang, Y . Liu, M. Broughton, I. Kim, A. Anshu, Z. Landau, and J. R. McClean, Learning shallow quantum circuits, (2024), arXiv:2401.10095

    2024 arXiv

  22. [30]

    Vasconcelos and H.-Y

    F. Vasconcelos and H.-Y . Huang, Learning shallow quantum circuits with many-qubit gates, (2024), arXiv:2410.16693

    2024 arXiv

  23. [31]

    Green, S

    F. Green, S. Homer, C. Moore, and C. Pollett, Count- ing, fanout, and the complexity of quantum ACC (2001), arXiv:quant-ph/0106017

    2001 arXiv

  24. [32]

    M. Reck, A. Zeilinger, H. J. Bernstein, and P. Bertani, Experimental realization of any discrete unitary operator, Phys. Rev. Lett. 73, 58 (1994)

    1994

  25. [33]

    Barenco, C

    A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. We- infurter, Elementary gates for quantum computation, Phys. Rev. A 52, 3457 (1995)

    1995

  26. [34]

    E. G. Rieffel and W. H. Polak, Quantum computing: A gentle introduction (MIT press, 2011)

    2011

  27. [35]

    Jerbi, A

    S. Jerbi, A. Cornelissen, M. Ozols, and V . Dunjko, Quan- tum policy gradient algorithms, in 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023), Leibniz International Proceed- ings in Informatics (LIPIcs), V ol. 266, edited by O. Fa...

    2023

  28. [36]

    [17], the Um,θ gates can be compiled into arbitrary one-qubit gates and two-qubit CNOT gates

    Circuit compilation of Um,θ Directly following the arguments put forward in Ref. [17], the Um,θ gates can be compiled into arbitrary one-qubit gates and two-qubit CNOT gates. Following the discussions in Ref. [28], any operator on m qubits can be performed with at most O(m34m)...

  29. [37]

    Construct ⃗V using M samples ⃗V = 1 m MX i=1 1 (parity(x(i)) = Yx(i) )⃗ e|x(i)| mod pp. (B9)

  30. [38]

    If none such k∗ is found, output failure

    Search in ⃗V for the position k∗, where (a) the entry at k∗ is τ-close to 1 2, (b) the entry at k∗ + 1 mod p is larger than 1 2 + τ. If none such k∗ is found, output failure

  31. [39]

    Output ˜s = p − k∗ mod p. In order for the algorithm to successfully find s, it is evident from Figure 2.c) that τ needs to be smaller than half of the difference between the two consecutive values ofcos2 − π 4 + π p (k + s) for k = p−s mod p and k = p−s+1 mod p. That is, τ is...

  32. [40]

    It follows that f is increasing to a maximum and then decreasing in the interval [0, 1 2 ]

    It can be easily verified that f ′(0) > 0 and f ′( 1 2 ) < 0, and f ′′(x) < 0 for x ∈ [0, 1 2 ]. It follows that f is increasing to a maximum and then decreasing in the interval [0, 1 2 ]. Since f (0) = 0 and f ( 1 3 ) > 0, it follows that f (x) ≥ 0 for x ∈ [0, 1 3 ]

Pith tools

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