Pith. sign in

REVIEW 4 major objections 5 minor 62 references

One Polynomial Strategy for Computing Local Projections on Square-Lattice Cluster States

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The paper claims a recursive trace-factorization strategy can evaluate arbitrary local projections on 2D square-lattice cluster states in polynomial steps with bounded memory, which would make each output amplitude of measurement-based…

desk verdict The trace-factorization trick is neat and correct in 1D, but the central 2D polynomial-time claim is explicitly non-strict, never derived, and unsupported by the data. read the letter →

arxiv 2506.14257 v1 pith:GQNCA542 submitted 2025-06-17 quant-ph

Nyau Fisn , Houren Fu This is my paper · ORCID
classification quant-ph MSC 81P68 PACS 03.67.Lx
keywords measurement-basedquantumcomputingclusterstateslocalprojectionsclassicalsimulationrecursivecontractiontensor-productfactorizationsquarelatticepolynomial-timealgorithm
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

This paper tries to establish that an arbitrary local projection on a two-dimensional square-lattice cluster state—one of the universal resources for measurement-based quantum computing—can be evaluated classically with a number of computational steps polynomial in the number of qubits N, using memory that does not grow with N. The proposed route is to factor the exponentially large projection sum into a trace of tensor-product brackets, then contract the brackets row by row with recursive relations. If the strategy is sound, every individual output amplitude of a universal measurement-based quantum computation becomes classically computable in polynomial time, which would bear directly on where the quantum computational advantage resides. The authors present the work as an informal note with easily checked examples, and explicitly flag that the 2D recursion is not yet a strict proof.

What carries the argument

The workhorse is a trace factorization identity. For projectors of the form (C⟨0| + S⟨1|), the naive sum over control-qubit configurations with 2^K terms is repackaged as the trace of a product of diagonal-matrix brackets, using U = (I + Z)/2 and D = (I − Z)/2 to convert the parity relation α_q = (sum of neighboring control bits) mod 2 into factors of the form (C I + S Z) or (C I ⊗ I + S Z ⊗ Z) on a tensor-product ring. Once the projection polynomial is in this factorized bracket form, the computation is contracted recursively along rows; the key structural assumption is that in each row only a bounded number of brackets contain non-identity matrices, so each recursion step depends only on a bounded number of previous results.

What would settle it

Implement the recursive contraction for rectangular 2D cluster states with, say, M = N = 4, 5, and 6, and compare every output amplitude with a direct state-vector inner product. The central claim is falsified if runtime or memory scales superpolynomially in N, or if the number of terms that must be retained between recursion steps grows with the lattice width; the paper's 12-qubit data alone cannot settle this, as the authors themselves note.

Watch

Extended reading notes

Core claim

The central claim is that for a 2D square-lattice cluster state with N qubits, the value of any local projection can be computed in a number of steps proportional to a polynomial of N under a bounded cost of memory. The argument proceeds by rewriting the cluster state as a tensor-product sum over control-qubit basis states, then factorizing the projection polynomial so that it becomes the trace of a product of bracketed factors such as (C I + S Z) in a tensor-product space built from {I, Z, U, D}. In the line-shape and cross-shape cases, the factorization yields exact O(N) recursions. For the full 2D lattice, the authors exhibit a block-structured factorized polynomial, argue that each row contains only a bounded number of effective factors, and conclude that local projections on the 2D extension of cross-shape cluster states—equivalent to the 2D square-lattice cluster states—can be computed in MN steps with bounded memory. The authors explicitly state that this 2D conclusion is not strict, because effective connections across blocks may disturb the recursive relations.

Load-bearing premise

The 2D recursion assumes that, after reordering factors, each step of the row-by-row contraction depends only on a bounded number of results from the previous step; the authors note that effective connections to factors in other blocks may disturb this, and if those connections make the retained representation grow with the lattice, the polynomial bounded-memory claim collapses.

Editorial extensions

If this is right

  • If the 2D recursion is valid, each individual amplitude of any measurement-based quantum computation on a square-lattice cluster state can be computed classically in polynomial time and bounded memory, instead of by summing exponentially many terms.
  • The recursive contraction means storage does not scale with N: only the results from the immediately preceding step need to be kept.
  • The numerical examples on 4-, 7-, and 12-qubit cluster states show the factorized and recursive evaluations matching exact state-vector inner products while running orders of magnitude faster, though the authors caution that these data cannot distinguish polynomial scaling from e^{N^γ} scaling.
  • The same bracket factorization extends, the authors suggest, to 3D cubic lattice cluster states built from 7- or 9-qubit GHZ units, potentially connecting to 3D Ising-model studies.
  • Because local projections on a universal cluster-state resource would then be classically polynomial-time computable, the note raises the question of whether the computational advantage of measurement-based quantum computing must come from something other than the efficient evaluation of a single output amplitude.

Reading between the lines

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

  • A decisive stress test is to grow both lattice dimensions and watch the number of cross-block terms carried between recursion steps; if that number grows with lattice width, the bounded-memory polynomial claim fails even though small examples look favorable.
  • The factorization relies on the CZ/parity structure that keeps every bracket in span({I, Z}); inserting non-Clifford rotations such as T gates would break the (C I + S Z) product form, so the method, if correct, targets the cluster-state resource itself rather than arbitrary circuit simulation.
  • Polynomial evaluation of single amplitudes would not by itself erase quantum advantage for sampling or distribution-generation tasks, since producing all 2^N amplitudes still costs exponential time; the paper's own discussion of Shor's algorithm implicitly concedes this point.
  • The bracket structure is closely related to tensor-network contraction, and viewing the 2D lattice as a tensor network suggests the hidden assumption is exactly a bounded-width effective bond dimension along the anti-diagonal contraction order.
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

4 major / 5 minor

Summary. The paper proposes a classical strategy for computing local projections (output amplitudes) on square-lattice cluster states by rewriting the projection polynomially as a trace of products of matrices built from I, Z, U, and D, and then evaluating the trace by recursion. For line-shape cluster states (Section II A) and one-dimensional extensions of cross-shape cluster states (Section II B), explicit recursions are given that evaluate the projection in O(N) arithmetic steps. The central claim, stated in the abstract and in Section II C, is that for a two-dimensional square-lattice cluster state (2DSLCS) an analogous recursive strategy computes an arbitrary local projection in a number of steps proportional to the number of qubits (O(MN) for an M×N lattice) while using bounded memory. The paper supports the 2D claim with a block-reordering argument and graphical patterns (Figs. 7–11), and with numerical tests on small systems containing 4, 7, and 12 qubits (Fig. 14).

Significance. If the 2D claim were correct, it would imply that individual output amplitudes of universal measurement-based quantum computation can be evaluated classically in polynomial time with constant memory, which would be a striking result relevant to the limits of quantum advantage and to classical simulation of cluster-state computations. The explicit one-dimensional derivations in Sections II A and II B are internally consistent and are useful as a pedagogical illustration of the trace-factorization trick; the small numerical check in Fig. 13 against direct inner products for a 3×3 2DSLCS is a genuine external verification of the factorization for that specific state. However, the load-bearing part of the paper—the polynomial bounded-memory claim for general 2DSLCSs—is not established. The authors explicitly label the 2D conclusion as 'NOT a strict one' and do not write down a general recursion; the numerical evidence is admittedly insufficient to distinguish polynomial from subexponential scaling. The current significance is therefore that of a conjecture with supporting examples, not a proven classical simulation algorithm.

major comments (4)
  1. [Section II C, paragraph after the three bullet points] The paper's central claim—that local projections on arbitrary 2DSLCSs can be computed in MN steps with bounded memory—is explicitly conceded not to be a strict result. The passage states: 'the above conclusion is NOT a strict one' and acknowledges that 'other than the effective connections to the bracketed factors in the next row, there are also effective connections to the factors in the row of other blocks. This fact causes some troubles for obtaining the recursive relations.' The authors only express the belief that this does not destroy the strategy. Since the abstract and Section V rest directly on this claim, the manuscript does not actually establish its main result.
  2. [Section II C, Eqs. (27)–(28) and Figs. 8–11] No explicit recursive relations are provided for the general 2D case. Equations (27) and (28) show how two particular bracketed factors transform under extension in two directions, but the text only says 'one may establish recursive relations by using the transformations deduced from the extensions.' A closed recursion with a proof that the number of retained coefficients is bounded independently of the lattice width M is never written down. Without such a width-independent recursion, the claimed O(MN) step count and bounded-memory property do not follow.
  3. [Section III, Fig. 14 and the accompanying paragraph] The numerical scaling evidence uses only 4, 7, and 12 qubits, and the authors themselves state that 'the scalings shown in Fig. 14 are not sufficient to verify the conclusions in Section II due to the lack of data' and that the running time 'could also be e^{N^γ} (with the qubit number N and the real number γ < 1).' The data therefore cannot distinguish polynomial growth from subexponential growth, and in particular cannot support the bounded-memory O(MN) claim; the pink and green curves are consistent with the conjecture but provide no confirmation of it.
  4. [Section II C, Fig. 8] The reordering of bracketed factors that underlies the proposed recursion replaces the original parameters C and S by formal parameters a and b without an explicit mapping. The paper calls this 'a lazy treatment' and states that 'the author does not provide an explicit relation between the parameters C and S in the previous expression and the parameters a and b in Fig. 8.' Because the subsequent recursive structure is derived from the reordered polynomial, the missing parameter mapping leaves a gap in the derivation: it is not shown that the reordered expression equals the original projection for a general 2DSLCS, so the recursion, even if found, might compute a different quantity.
minor comments (5)
  1. [Section I, third paragraph] In the sentence describing the division of lattice vertices, 'severing' should be 'serving'; the same section also contains 'frankly, the expression of aq' where 'frankly' is likely a word-choice error.
  2. [Section II C, paragraph before Eq. (27)] The notation N is overloaded: at the start of Section II C the paper says 'N is used to describe the number of columns only in this subsection,' while in the abstract and elsewhere N denotes the total number of qubits. This is confusing, particularly because the abstract's polynomial-in-N claim is the one being evaluated.
  3. [Section III, second example] The phrase 'ruining time' should be 'running time'; the same misspelling appears in the description of Fig. 14's vertical axis.
  4. [Section IV, item 6] The phrase 'the idea of renormalization asartz to the 2-D Ising models' contains the typo 'asartz,' which appears to be intended as 'ansatz' or 'as a start.'
  5. [References] Reference [15] contains the typo 'reivew' for 'review'; reference [46] cites a Wikipedia page, which is not a stable or standard literature source for a formal paper.

Circularity Check

0 steps flagged · score 1.0 of 10

No circular derivation: the factorizations are exact algebraic rewritings checked against direct inner products, and the 2D polynomial claim is an openly admitted unproven conjecture rather than a fitted or self-referential result.

full rationale

The paper's core derivation factorizes the projection polynomial (Eq. (4)) into products of matrices built from I, Z, U, and D using U=(I+Z)/2 and D=(I-Z)/2. This is an exact rewriting rather than a fit: the angles C_p and S_p remain free inputs, and no constants are tuned to match target outputs. The 1D recursive relations (Eqs. (15) and (26)) are obtained by carrying the bracketed products and taking traces, so they follow from the algebra rather than from the conclusions they are used to support. In Section III, the factorized trace for a 3-by-3 2DSLCS is numerically compared against direct inner products of 2^9-dimensional vectors (Fig. 13), providing an external validation that does not presuppose the factorized form. The central 2D claim, that local projections can be computed in MN steps with bounded memory, is explicitly not established by the authors: "the above conclusion is NOT a strict one... there are also effective connections to the factors in the row of other blocks. This fact causes some troubles for obtaining the recursive relations. However, we believe that it does not destroy the above strategy." This is a derivation gap and a correctness risk, not circularity: the missing ingredient is a width-independent recursion, not an output that has been defined as an input or a fitted parameter renamed as a prediction. The self-citations (Refs. [42], [43], and [47]) are background, inspiration, or application context, and are not the load-bearing justification for the factorization or the recursion. The numerical scaling plots in Fig. 14 are also explicitly conceded to be insufficient to distinguish polynomial from e^{N^gamma} behavior, so they are not used as a fitted prediction that closes the argument. Overall, the paper's main weakness is incompleteness rather than circular reasoning.

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

No free parameters are fitted; the core factorization is checked against direct inner products for small lattices. The main burden is the unproved 2D recursion, listed as an ad hoc assumption.

assumptions (3)
  • ad hoc to paper The 2D block trace pattern can be reduced by pairwise multiplication of effective factors so that each row of the lattice feeds a bounded number of quantities into the next row.
    Invoked in Section II C to claim the recursive relations hold for the 2D extension; the authors state the conclusion is "NOT a strict one" and that cross-block connections cause trouble.
  • standard math The set span({I,Z} tensor power N) is closed under multiplication and trace, which underlies the factorized polynomial representation.
    Used in Section II C to justify expanding the brackets in blocks and taking traces of products of diagonal Pauli operators.
  • domain assumption Universal quantum computation can be implemented using only local projections on 2D square-lattice cluster states.
    Used in Section IV.2 to argue that a polynomial projection algorithm would shortcut all quantum algorithms and potentially collapse complexity classes.

how reviews work

0 comments
Cite this review

Pith. "Pith review of One Polynomial Strategy for Computing Local Projections on Square-Lattice Cluster States." pith.science (2026). https://pith.science/paper/GQNCA542

@misc{pith2026250614257,
  author       = {Pith},
  title        = {Pith review of: One Polynomial Strategy for Computing Local Projections on Square-Lattice Cluster States},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GQNCA542}},
  note         = {Machine review of arXiv:2506.14257}
}
abstract

Quantum computing has attracted a lot of attention in recent years. It is one of the promising candidates for the next-generation computing paradigms. Basically, there are two technical lines to realize quantum computing. One is composing the unitary operators of a few qubits to achieve general unitary operators on an arbitrary number of qubits, known as the approach of quantum circuits. The other one focuses on preparing quantum cluster states and performing the computation by measuring the states with a particular basis, known as measurement-based quantum computing or one-way quantum computing. The two strategies have been proven to be equivalent to each other. This note aims to discuss the strategies for computing the local projections on square-lattice cluster states. Seemingly, one strategy for the computation could require both polynomial steps and memories. In particular, if the number of qubits in a square-lattice is denoted by $N$, the step number for computing an arbitrary local projection on the state could be proportional to a polynomial of $N$ under a bounded cost of memory. Consider that the square-lattice cluster states are one kind of universal computing resource, the results might be helpful for understanding the computational advantages of quantum algorithms, as well as the limits of the numerical analysis on other relevant quantum models. Although the results in the note are not peer reviewed, we would like to make them public because they are quite easy to check.

Figures

Figures reproduced from arXiv: 2506.14257 by the authors.

Figure 1
Figure 1. FIG. 1. The graph of a 2DSLCS, with the qubits as the [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2. The extension of line-shape cluster states. [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 4
Figure 4. FIG. 4. A 1-D extension of the cross-shape state. [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figures from the paper (13 more)
Figure 6
Figure 6. Figure 6: FIG. 6. A graphic illustration of a 2-D extension of the cross [PITH_FULL_IMAGE:figures/full_fig_p006_6.png]
Figure 7
Figure 7. Figure 7: FIG. 7. The factorized polynomial form of projection on the 2DSLCS in Fig. [PITH_FULL_IMAGE:figures/full_fig_p007_7.png]
Figure 8
Figure 8. Figure 8: FIG. 8. A form of the polynomial in Fig. [PITH_FULL_IMAGE:figures/full_fig_p009_8.png]
Figure 9
Figure 9. Figure 9: FIG. 9. The process of distributing the terms across four [PITH_FULL_IMAGE:figures/full_fig_p009_9.png]
Figure 10
Figure 10. Figure 10: FIG. 10. One way of distributing the terms across the brack [PITH_FULL_IMAGE:figures/full_fig_p010_10.png]
Figure 11
Figure 11. Figure 11: FIG. 11. Another way of distributing the terms across the [PITH_FULL_IMAGE:figures/full_fig_p010_11.png]
Figure 12
Figure 12. Figure 12: FIG. 12. The factorization of projection on a finite 2DSLCS in the right corner of the bottom. The matrices [PITH_FULL_IMAGE:figures/full_fig_p012_12.png]
Figure 13
Figure 13. Figure 13: FIG. 13. The factorization form of the projection on a 3-by-3 [PITH_FULL_IMAGE:figures/full_fig_p012_13.png]
Figure 15
Figure 15. Figure 15: FIG. 15. The circuits for generating the cluster states in Fig. [PITH_FULL_IMAGE:figures/full_fig_p013_15.png]
Figure 16
Figure 16. Figure 16: FIG. 16. The polynomials for computing the cluster states [PITH_FULL_IMAGE:figures/full_fig_p014_16.png]
Figure 17
Figure 17. Figure 17: FIG. 17. Two kinds of 3-D cubic lattice cluster states. The [PITH_FULL_IMAGE:figures/full_fig_p016_17.png]
Figure 18
Figure 18. Figure 18: FIG. 18. The mapping relations of MBQC and a universal [PITH_FULL_IMAGE:figures/full_fig_p017_18.png]
Figure 19
Figure 19. Figure 19: FIG. 19. A step-by-step procedure for obtaining the cluster [PITH_FULL_IMAGE:figures/full_fig_p017_19.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

62 extracted references · 53 canonical work pages

  1. [1]

    Especially, a matrix product state (MPS) in the tool box is defined by [32] |ψM P S⟩ = 1X j1,j2,...,jN Θj1,j2,...,jN |j1,

    Again, we realize that the method in this note is very similar to the tensor network method for quantum com- puting [33]. Especially, a matrix product state (MPS) in the tool box is defined by [32] |ψM P S⟩ = 1X j1,j2,...,jN Θj1,j2,...,jN |j1, . . . , jN ⟩, (36) where Θj1,j2,...,jN = X α,β,... Aα,j1,j2 Bβ,j3,j4 . . . . (37) In other words, the basis ampli...

    work page

  2. [2]

    shortcut

    It is known that a 2DSLCS is one kind of universal quantum computing resource, meaning that any type of quantum algorithm can be implemented using the state. To the best of our knowledge, only local projectors are required for performing universal quantum computing. If this is precise, a polynomial strategy for computing the projection results of 2DSLCS c...

    work page

  3. [3]

    A famous example of the quantum advance is the efficiency of running the Shor’s algorithm [5] for integer factorization. One typical character of quantum states involved in the Shor’s algorithm is that, for the output state of the quantum Fourier transform (QFT) subrou- tine, the measurements on the state would give the pe- riod of the modular exponential...

    work page

  4. [4]

    A prime example is Simon’s algorithm [4], which demonstrates an exponen- tial speedup compared to its classical counterparts and serves as the inspiration of Shor’s algorithm [46]

    Going a bit further, it is well known that the quan- tum advantage in query complexity represents a signifi- cant revolution in algorithm design. A prime example is Simon’s algorithm [4], which demonstrates an exponen- tial speedup compared to its classical counterparts and serves as the inspiration of Shor’s algorithm [46]. Cru- cially, it can be rigorou...

    work page

  5. [5]

    As indicated in Ref

    We notice that machine learning can also be per- formed using the strategy in the note. As indicated in Ref. [47], the learning of a data set can be performed us- ing a 2DSLCS. In such a formulism, the input data is en- coded by the qubits of the 2DSLCS. Compared with the total state, the number of qubits that carry input data is very small. The outputs a...

    work page

  6. [6]

    In fact, the idea of MBQC is related to the investigations on 2-D Ising mod- els

    Despite being a bit far from the topic, we would like to mention the 3-D Ising model [48]. In fact, the idea of MBQC is related to the investigations on 2-D Ising mod- els. In an Ising model, the interactions among spins are Z-Z couplings. Hence, the evolution operator of a pair of spins for a given time is also known as ZZ rotation gates in quantum compu...

    work page

  7. [7]

    directions

    As explained in the caption, the author does not pro- vide an explicit relation between the parameters C and S in the previous expression and the parameters a and b in Fig. 8. It is just a reordering of the factors, so one can formally have the expression. As shown above, the recur- sive relations can be obtained by distributing the terms across the brack...

    work page

  8. [8]

    freshman

    Finally, we would like to mention another interesting but not-so-well-known theorem called “freshman” theo- rem (or “a freshman’s dream”). The story comes from a common mistake for freshmen in computing the expres- sion (x + y)n. Certainly, if one distributes all the terms 16 FIG. 17. Two kinds of 3-D cubic lattice cluster states. The unit cluster state o...

    work page

Show all 62 references
  1. [9]

    good choice of space

    Actually, many of the Feynman’s ideas have shown the spirit of question. An example is the Feynman’s trick on integration. For the integral like R ∞ 1 x5exdx, one can define a function I(a) = R ∞ 1 e−axdx = −ea/a. Then, the integral can be evaluated by computing the fifth orde...

  2. [10]

    R. P. Feynman. Simulating physics with computers. Int. J. Theor. Phys.21, 467 (1982)

    1982

  3. [11]

    D. Deutsch. Quantum theory, the Church-Turing princi- ple and the universal quantum computer. Proc. R. Soc. Lond. A, 400 (1818): 97-117, (1985)

    1985

  4. [12]

    Bernstein & U

    E. Bernstein & U. Vazirani. Quantum complexity theory. SIAM J. Comput., 26(5):1411-1473, (1997)

    1997

  5. [13]

    D. R. Simon. On the power of quantum computation. SIAM J. Comput., 26(5):1474-1483, (1997)

    1997

  6. [14]

    P. W. Shor. Polynomial-time algorithms for prime factor- ization and discrete logarithms on a quantum computer. SIAM Rev., 41(2):303-332, (1999)

    1999

  7. [15]

    L. K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett.79, 325 (1997)

    1997

  8. [16]

    P. W. Shor. Scheme for reducing decoherence in quantum computer memory. Phys. Rev. A 52(4): R2493, 1995

    1995

  9. [17]

    Preskill

    J. Preskill. Quantum computing 40 years later. arXiv: 2106.10522v3

    arXiv

  10. [18]

    C. Oh, K. Noh, B. Fefferman, & L. Jiang, Classical sim- ulation of lossy boson sampling using matrix product op- erators. Phys. Rev. A 104, 022407 (2021)

    2021

  11. [19]

    Aaronson & D

    S. Aaronson & D. Gottesman. Improved simulation of stabilizer circuits. Phys. Rev. A70, 052328 (2004)

    2004

  12. [20]

    M. V. Nest. Classical simulation of quantum computa- tion, the Gottesman-Knill theorem, and slightly beyond. Quant. Inf. Comp.10, 0258-0271 (2010)

    2010

  13. [21]

    G. Vidal. Efficient simulation of one-dimensional quan- tum many-body systems. Phys. Rev. Lett. 93, 040502 (2004)

    2004

  14. [22]

    G. Vidal. Entanglement renormalization. Phys. Rev. Lett. 99, 220405 (2007)

    2007

  15. [23]

    G. Vidal. Class of quantum many-body states that can be efficiently simulated. Phys. Rev. Lett. 101, 110501 (2008)

    2008

  16. [24]

    R´ edei and S

    M. R´ edei and S. J. Summers. Quantum probability theory. arXiv: quant-ph/0601158v3 (2006). This paper reivew the quantum probability theory—a theory that views the quantum theory as a probability theory under different axioms. In such a sense, the relation between the quantum...

    2006 arXiv

  17. [25]

    Neville, C

    A. Neville, C. Sparrow, R. Clifford, E. Johnston, P. M. Birchall, A. Montanaro & A. Laing. Classical boson sam- pling algorithms with superior performance to near-term experiments. Nat. Phys. 13, 1153–1157 (2017)

    2017

  18. [26]

    Jiang, & B

    K Noh, L. Jiang, & B. Fefferman. Efficient classical sim- ulation of noisy random quantum circuits in one dimen- sion. Quantum 4, 318 (2020)

    2020

  19. [27]

    van de Wetering

    J. van de Wetering. ZX-calculus for the working quantum computer scientist. arXiv: 2012.13966 (2020). This paper introduces a graphic representation of a quantum circuit, which might not directly related to the topic in this note. While, the author thinks that it provide a dif...

    2020 arXiv

  20. [28]

    C. Oh, B. Fefferman, L. Jiang, & N. Quesada. Quantum- inspired classical algorithm for graph problems by gaus- sian boson sampling. PRX Quant. 5, 020341 (2024)

    2024

  21. [29]

    C. Oh, M. Liu, Y. Alexeev, B. Fefferman & L. Jiang. Classical algorithm for simulating experimental Gaussian boson sampling. Nat. Phys. 20, 1461–1468 (2024)

    2024

  22. [30]

    Chia, H.-H

    N.-H. Chia, H.-H. Lin, & C. Wang, Quantum-inspired sublinear classical algorithms for solving low-rank linear systems. arXiv: 1811.04852 (2018)

    2018 arXiv

  23. [31]

    Gily´ en, S

    A. Gily´ en, S. Lloyd, & E. Tang. Quantum-inspired low- rank stochastic regression with logarithmic dependence on the dimension. arXiv: 1811.04909 (2018)

    2018 arXiv

  24. [32]

    E. Tang. A quantum-inspired classical algorithm for rec- ommendation systems. arXiv: 1807.04271 (2018)

    2018 arXiv

  25. [33]

    E. Tang. Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions. Phys. Rev. Lett.127, 060503 (2021)

    2021

  26. [34]

    Kalachev, P

    G. Kalachev, P. Panteleev, P. Zhou, & M.-H. Yung. Clas- sical sampling of random quantum circuits with bounded fidelity. arXiv: 2112.15083 (2021)

    2021 arXiv

  27. [35]

    F. Pan, K. Chen, & P. Zhang. Solving the sampling prob- lem of the sycamore quantum circuits. Phys. Rev. Lett. 129, 090502 (2022)

    2022

  28. [36]

    Z. Ma, T. Tian, Y. Liao, X. Feng, Y. Li, K. Cui, F. Liu, H. Sun, W. Zhang, & Y. Huang. Electrically switch- able 2N-channel wave-front control for certain function- alities with N cascaded polarization-dependent metasur- faces. Nat. Commun. 15, 8370 (2024)

    2024

  29. [37]

    Gulbahar

    B. Gulbahar. Quantum path computing: computing architecture with propagation paths in multiple plane diffraction of classical sources of fermion and boson parti- cles. arXiv: 1709.00735v4 (2019). This paper introduces an interesting scheme on the mimic of quantum compu- tation...

    2019 arXiv

  30. [38]

    Yang & X.-B

    T.-Y. Yang & X.-B. Wang. Speeding up the classical sim- ulation of Gaussian boson sampling with limited connec- tivity. Sci. Rep. 14, 7680 (2024)

    2024

  31. [39]

    Atallah, M

    S. Atallah, M. Garn, S. Jevtic, Y. Tao, & S. Virmani. Ef- ficient classical simulation of cluster state quantum cir- cuits with alternative inputs. Quantum 8, 1243 (2024). The topic of the paper is similar to the note, but the method is different

    2024

  32. [40]

    Martinez, A

    V. Martinez, A. Angrisani, E. Pankovets, O. Fawzi, D. S. Fran¸ ca. Efficient simulation of parametrized quantum circuits under non-unital noise through Pauli backprop- agation. arXiv: 2501.13050 (2025)

    2025 arXiv

  33. [41]

    R. Or´ us. A practical introduction to tensor networks: Matrix product states and projected entangled pair states. Ann. Phys. 349, 117-158 (2014)

    2014

  34. [42]

    Berezutskii, A

    A. Berezutskii, A. Acharya, R. Ellerbrock, J. Gray, R. Haghshenas, Z. He, A. Khan, V. Kuzmin, M. Liu, D. Lyakh, D. Lykov, S. Mandr` a, C. Mansell, A. Melnikov, A. Melnikov, V. Mironov, D. Morozov, F. Neukart, A. No- cera, M. A. Perlin, M. Perelshtein, R. Shaydulin, B. Vil- lal...

    2025

  35. [43]

    T. B. Wahl & S. Strelchuk. Simulating quantum cir- cuits using efficient tensor network contraction algo- rithms with subexponential upper bound. Phys. Rev. Lett. 131, 180601 (2023)

    2023

  36. [44]

    Masot-Llima & A

    S. Masot-Llima & A. Garcia-Saez. Stabilizer tensor net- works: universal quantum simulator on a basis of stabi- lizer states. Phys. Rev. Lett.133, 230601 (2024)

    2024

  37. [45]

    However, a curve should have tangent lines with slopes bigger than 1 if it could be fitted by N γ

    If the green and pink curves could be fitted by N γ, the scaling of the running time would be eN γ . However, a curve should have tangent lines with slopes bigger than 1 if it could be fitted by N γ. Albeit the slopes of the fitted lines here are far less than 1, it is still h...

  38. [46]

    Gabrielli, D

    A. Gabrielli, D. Garlaschelli, S. P. Patil, & M. ´A. Serrano. Network renormalization. Nat. Rev. Phys. 7, 203–219 (2025)

    2025

  39. [47]

    Klinkenberg, C

    L. Klinkenberg, C. Blumenthal, M. Chen, D. Haase, & J.-P. Katoen. Exact Bayesian Inference for Loopy Probabilistic Programs using Generating Functions. arXiv:2307.07314 (2023)

    2023 arXiv

  40. [48]

    Raussendorf & H

    R. Raussendorf & H. J. Briegel. A one-way quantum com- puter. Phys. Rev. Lett. 86, 5188 (2001)

    2001

  41. [49]

    Raussendorf, D

    R. Raussendorf, D. E. Browne, & H. J. Briegel. Measurement-based quantum computation on cluster states. Phys. Rev. A68, 022312 (2003)

    2003

  42. [50]

    The limits of my language mean the limits of my world

    Cheers to dancing in chains, right? Ending with a famous quote from the book Tractatus Logico-Philosophicus written by Ludwig J. J. Wittgen- stein: Die Grenzen meiner Sprache bedeuten die Grenzen meiner Welt. It means “The limits of my language mean the limits of my world” in ...

  43. [51]

    The author does not check the case strictly

    The factorization of the polynomial seems not to be valid on the complex number field either, i.e., a, b, c, d∈ C. The author does not check the case strictly. It can be seen from the solvability of the equation set obtained by expanding the assumed factorized form and letting...

  44. [52]

    Y. Sun, X. Song, H. Qin, X. Zhang, Z. Yang, & X. Zhang. Non-local classical optical correlation and imple- menting analogy of quantum teleportation. Sci. Rep. 5, 9175 (2015). 20

    2015

  45. [53]

    Y. Sun, Q. Li, L.-J. Kong, J. Shang, & X. Zhang. Uni- versal classical optical computing inspired by quantum information process. Ann. Phys. (Berlin), 2200360 (2022)

    2022

  46. [54]

    A typical example is the interpolation and approximation (of a polynomial) based on Cheby- shev polynomials

    A problem of recursive algorithms is that the error, if any, in one step will accumulate easily through out the whole calculation. A typical example is the interpolation and approximation (of a polynomial) based on Cheby- shev polynomials. It is known that there are a series o...

  47. [55]

    ht tps://en.m.wikipedia.org/wiki/Simon%27s_problem

    The instruction about Simon’s problem on Wikipedia. ht tps://en.m.wikipedia.org/wiki/Simon%27s_problem

  48. [56]

    Sun, & X

    Y. Sun, & X. Zhang. Measurement-based quantum con- volutional neural network for deep learning. ArXiv: 2412.08207 (2024)

    2024 arXiv

  49. [57]

    G. M. Viswanathan, M. A. G. Portillo, E. P. Raposo, & M. G. E. da Luz. What does it take to solve the 3D Ising model? Minimal necessary conditions for a valid solution. arXiv: 2205.12357 (2022)

    2022 arXiv

  50. [58]

    This inter- esting formula can be found on http://kawaihome.link /jbooks/qcomp-short/q2gates/cz.html

    UCZ = e−iπ/4(e−iZπ/ 4 ⊗ e−iZπ/ 4)e−iZ⊗Zπ/ 4. This inter- esting formula can be found on http://kawaihome.link /jbooks/qcomp-short/q2gates/cz.html

  51. [59]

    pockets of reducibility

    It is similar to the concept “pockets of reducibility” brought by Stephen Wolfram. This can be found in the blog entitled by “What Is Consciousness? Some New Perspectives from Our Physics Project”. Stephen Wol- fram Writings. (2021) https://writings.stephenwolf ram.com/2021/03...

    2021

  52. [60]

    E. T. Campbell & J. Fitzsimons. An introduction to one- way quantum computing in distributed architectures. ArXiv:0906.2725v2 (2009)

    2009 arXiv

  53. [61]

    Gates, States, and Circuits: Quantum Gates

    An interesting and comprehensive tool box can be found in the note by G. E. Crooks, entitled by “Gates, States, and Circuits: Quantum Gates” (Version: Tech. Note 014 v0.11.0 beta). (2024) https://threeplusone.com/pub s/on_gates.pdf

    2024

  54. [62]

    They are differently defined in their sections, respectively

    Please do not mix them with the notations in Section II B and II C, and Section III. They are differently defined in their sections, respectively

Pith tools

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