Pith. sign in

REVIEW 3 major objections 4 minor 25 references

Quantum State Preparation Based on LimTDD

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read The paper claims that any n-qubit state representable by a LimTDD with p reduced paths is preparable by a circuit generated in O(np) time, using O(n^2p) three-qubit gates plus O(np) two-qubit gates.

desk verdict A clever node-based QSP algorithm for LimTDD that is likely sound for unitary edge weights, but the paper's 'any subgroup of M' claim is false as stated. read the letter →

arxiv 2507.14496 v1 pith:EMFVAESM submitted 2025-07-19 quant-ph cs.DS

Xin Hong , Chenjian Li , Aochu Dai , Sanjiang Li , Shenggang Ying , Mingsheng Ying This is my paper
classification quant-phcs.DS
keywords quantumstatepreparationLimTDDdecisiondiagramstensornetworkscircuitsynthesisgatecomplexitylocalinvertiblemaps
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

The paper claims that any $n$-qubit state whose amplitudes are organised by a LimTDD—a decision diagram whose edges carry local invertible $2\times 2$ matrices—can be prepared by a circuit whose size is controlled by the diagram's number of reduced paths $p$ rather than by $2^n$. Concretely, it gives an algorithm that runs in $O(np)$ time and produces $O(n^2p)$ three-qubit gates, $O(np)$ two-qubit gates, and some higher-controlled gates, with only $O(n)$ single-qubit gates. For states such as the constructed $|v_n\rangle$ family, the LimTDD has one reduced path, so the circuit has $O(n^2)$ gates, while the ADD-based decision-diagram method and the general-purpose frameworks compared in the paper need exponentially many gates; in the $n=15$ experiments the gap is about 100 gates against roughly 130,000. If correct, this turns compact graphical structure directly into small circuits, which matters because state preparation is a bottleneck for many quantum algorithms. The paper also reports experiments on randomly generated Clifford+T states showing lower gate counts and runtimes than the compared methods at larger qubit counts.

What carries the argument

The central object is the LimTDD (Local Invertible Map Tensor Decision Diagram): a rooted, weighted, directed acyclic graph whose non-terminal nodes carry qubit indices, whose edges carry weights in a subgroup of tensor products of invertible $2\times 2$ matrices, and whose semantics are $|v\rangle = |0\rangle|low(v)\rangle + |1\rangle|high(v)\rangle$ with edge weights applied as operators. The quantity that carries the complexity is the number $p$ of reduced paths, obtained by merging edges between nodes. The load-bearing mechanism is a set of three reduction observations: applying the adjoint of the incoming edge operator cancels that operator; applying the adjoint of a high-edge operator, controlled by the ancilla and the node's qubit, cancels that edge operator; and when both successors coincide, a $2\times 2$ unitary built from the edge weights maps the outgoing weights to $[1,0]$. An ancilla qubit controlled by branch conditions marks sub-diagrams open or closed so these local reductions can be applied to every node as if it were the root.

What would settle it

Represent the one-qubit state $(|0\rangle+|1\rangle)/\sqrt{2}$ by a LimTDD whose incoming edge weight is the invertible, non-unitary shear $O = \begin{pmatrix}1&1\\0&1\end{pmatrix}$ applied to the child $|1\rangle$, with scalar $\lambda=1/\sqrt{2}$. The algorithm's first step would cancel $O$ by applying $O^\dagger$, but $O^\dagger$ is not unitary and $O^\dagger O|1\rangle = |0\rangle+2|1\rangle \neq |1\rangle$, so the reduction fails and the inverse circuit does not prepare the target state. This directly tests the claim that the algorithm works for every subgroup of the local invertible map group.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that a LimTDD's compression can be exploited operationally: each reduced path in the diagram is traversed exactly once in depth-first order, and every edge operator and complex weight along the path is eliminated while an ancilla keeps unprocessed branches closed. The algorithm first cancels the operator on the root's incoming edge, then recursively cancels high-edge operators with controlled adjoints, processes the 0- and 1-successors by opening and closing nodes using branch conditions, and finally reduces the outgoing edge weights to $[1,0]$ with a controlled $2\times 2$ unitary. The circuit that maps the represented state to $|0\cdots 0\rangle$ is then inverted to prepare the target state from $|0\cdots 0\rangle$. The paper claims worst-case complexities of $O(np)$ runtime, $O(n^2p)$ three-qubit gates, and $O(np)$ two-qubit gates; in the tower case where the two successors of every node coincide, only $O(n^2)$ two-qubit gates are needed.

Load-bearing premise

The load-bearing premise is that every edge operator cancelled by the algorithm is unitary, since the algorithm applies its adjoint as a quantum gate; LimTDD itself only guarantees that edge operators are invertible $2\times 2$ matrices.

Editorial extensions

If this is right

  • Any state with $p$ reduced paths in a LimTDD is preparable in $O(np)$ time, so the exponential dependence on $n$ is shifted to the structural size $p$ of the diagram.
  • For tower-form LimTDDs, where the 0- and 1-successors of every node coincide, the preparation circuit uses only $O(n^2)$ two-qubit gates and $O(n)$ single-qubit gates.
  • For the constructed family $|v_n\rangle$, the LimTDD has one reduced path, so the circuit has $O(n^2)$ gates, while the compared decision-diagram and general-purpose baselines require exponentially many gates.
  • The circuits produced are deterministic inversions of a reduction circuit; the paper reports that, including transpilation time, the method overtakes the compared baselines in runtime as the qubit count grows past about ten.

Reading between the lines

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

  • An implication the paper leaves implicit is that its complexity analysis transfers directly from diagram size to circuit size: any state family with polynomial-size LimTDDs and exponential-size ADDs would inherit the exponential gate-count gap. That transfer is an inference from the paper's analysis, not a separate claim of the paper.
  • The paper defines edge weights as arbitrary invertible maps, but the cancellation steps are only physical for unitary weights; a natural next step is to restrict the subgroup to unitaries and test how much LimTDD compactness is lost, a trade-off the paper does not address.
  • The same ancilla 'open node' technique could be adapted to other structured state representations whose local maps are unitary, such as tensor networks with gauge freedoms, by treating each preserved sub-tensor as an open node. This is an extrapolation beyond LimTDD itself.
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 / 4 minor

Summary. The paper proposes a quantum state preparation algorithm based on LimTDD, a decision diagram with local invertible map edge weights. The algorithm uses an ancilla to mark the currently open branch, recursively cancels edge operators by applying their adjoints, and reduces complex edge weights to a canonical form. The authors claim that for an n-qubit state with p reduced paths the synthesis runs in O(np) time, produces O(n^2p) three-qubit gates and O(np) two-qubit gates, and that a constructed state |v_n> can be prepared with O(n^2) gates, exponentially beating ADD-based methods, Qiskit, and QuICT. The paper includes a worked 3-qubit example, a complexity analysis, and experiments comparing gate counts and runtime against prior methods.

Significance. If the correctness and complexity claims can be made rigorous, the paper would make a useful contribution: it gives a concrete recursive synthesis strategy that exploits a very compact tensor-network/decision-diagram representation, with a clear example showing a possible exponential gate-count advantage over ADD-based preparation. The paper is not circular: the algorithm does not fit parameters or assume its own efficiency; the main risk is an overgeneralization about the admissible edge operators. The authors provide explicit pseudocode and a step-by-step example, which is a strength, although no machine-checked proofs or reproducible code are supplied. The value of the work depends on whether the algorithm is restricted to genuinely unitary edge weights or the non-unitary case is handled with a valid decomposition.

major comments (3)
  1. [III-A (Definitions 1-2) and IV-A (Observations 1-2), Algorithm 1 lines 6 and 22] Observations 1 and 2 cancel an edge operator O by applying O†, but Definitions 1 and 2 allow O to be any invertible 2x2 matrix, not necessarily unitary. For non-unitary O, O† is not a unitary gate and O†O≠I, so the claimed reduction fails; for example, with O=diag(1,2) and |v>=|+>, O†O|v> is not proportional to |v>. The statement in Section III-A that the algorithm 'works for any subgroup of M' is therefore false as written, and the correctness of Algorithm 1 and the complexity theorem in Section VI inherit this problem. The authors should either restrict G to a unitary subgroup (the XP-Operators of [23] may be sufficient), or prove that every state-representing LimTDD can be rewritten with edge weights in a unitary subgroup; the gate-complexity analysis in Section VI-B also presupposes a concrete decomposition of edge operators into 3-qubit gates that is not justified for arbitrary invertible 2x2 matrices.
  2. [IV-A (Observation 3) and Algorithm 1, line 21] Observation 3 explicitly assumes w0≠0, but Algorithm 1 computes c=w1/w0 without a case split. A node whose low branch has zero amplitude is a legitimate quantum state and causes division by zero, so the algorithm as written does not cover all inputs. Add a branch for w0=0 (an X gate on the node qubit reduces that case to the same canonical form) or state and justify an invariant that w0 is never zero.
  3. [VII (Experiments)] The runtime comparisons are not reliable as reported: Section VII-A states that the ADD-based method ran on a different machine (13th Gen i5-13600KF, 32GB) from the other methods (11th Gen i7-11700F, 16GB), and the 20 random states per n are reported without seeds, error bars, or standard deviations. The gate-count claims are less affected, but the runtime claims such as 'completes in an average of 0.5 seconds' lack statistical support. Please provide seeds, per-instance data, code/data availability, and comparable hardware across all methods.
minor comments (4)
  1. [V-B, steps 4-6] The controlled-U and controlled-V gates are described only in prose; please specify their control and target qubits explicitly so the example can be checked independently of Fig. 3.
  2. [Throughout] There are numerous LaTeX/formatting artifacts in the displayed equations (e.g., '1√6', '−1√6', malformed fractions in Section V); these should be cleaned before publication.
  3. [VI-A and Definition 3] The complexity argument says there are n non-terminal nodes on a path, but the notion of 'reduced path' in Definition 3 may skip levels when successors are merged; please define exactly which path is counted in the O(np) bound.
  4. [VII-D] The constructed state |v_n> is described as having 'one path' in the LimTDD while the ADD representation has exponentially many paths; this sentence is correct only for the reduced-path notion used in the paper and should be stated with that qualification.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the LimTDD state-preparation algorithm's O(np)/O(n^2p) guarantees are construction-based bounds parameterized by the representation's reduced-path count, not fitted inputs renamed as predictions.

full rationale

The paper's derivation chain is self-contained. Section III defines LimTDD and reduced paths, and Section IV's Algorithm 1 traverses the diagram depth-first, cancelling edge weights and returning the inverse circuit; Section VI then counts this traversal to obtain O(np) time and O(n^2p) three-qubit gates as a function of the number p of reduced paths. This is a parameterized complexity statement derived directly from the construction, not a fitted parameter or an empirical prediction. The claimed practical advantage over ADD/Qiskit/QuICT rests on LimTDD compactness, and although that compactness is motivated by the same authors' prior paper [23], the current paper supplies an independent witness: the |v_n> example with one LimTDD path and exponentially many ADD paths. Thus the self-citation is not load-bearing for the main result. Separately, Observations 1-2 apply O^dagger to cancel arbitrary edge operators in M; because Definition 1 admits non-unitary invertible 2x2 maps, that generality claim is not supported (O^dagger O = I only for unitary O). This is a correctness/rigor defect, not a circularity, so it does not change the circularity score.

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

The central complexity claim rests on two premises the paper does not pay for: that LimTDD edge weights are unitary so their adjoints are valid cancellation gates, and that the input LimTDD is already available at negligible cost. No free parameters are fitted and no new entities are introduced.

assumptions (2)
  • domain assumption Edge weights in the LimTDD are unitary (or scalar multiples of unitary) so that O† is a valid quantum gate and cancels O.
    Definition 1 defines LIMs as invertible, not unitary, while Observations 1 and 2 in Section IV apply O† as a gate, which is only valid for unitary operators.
  • domain assumption The input to the algorithm is an already-constructed LimTDD; the cost of converting a state vector or circuit into LimTDD form is not part of the complexity.
    Algorithm 1 takes a node v as input, and Section VII mentions an interface converting state vectors to LimTDDs but gives no complexity; if conversion is expensive, total QSP cost may not match the advertised gain for vector inputs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum State Preparation Based on LimTDD." pith.science (2026). https://pith.science/paper/EMFVAESM

@misc{pith2026250714496,
  author       = {Pith},
  title        = {Pith review of: Quantum State Preparation Based on LimTDD},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EMFVAESM}},
  note         = {Machine review of arXiv:2507.14496}
}
read the original abstract

Quantum state preparation is a fundamental task in quantum computing and quantum information processing. With the rapid advancement of quantum technologies, efficient quantum state preparation has become increasingly important. This paper proposes a novel approach for quantum state preparation based on the Local Invertible Map Tensor Decision Diagram (LimTDD). LimTDD combines the advantages of tensor networks and decision diagrams, enabling efficient representation and manipulation of quantum states. Compared with the state-of-the-art quantum state preparation method, LimTDD demonstrates substantial improvements in efficiency when dealing with complex quantum states, while also reducing the complexity of quantum circuits. Examples indicate that, in the best-case scenario, our method can achieve exponential efficiency gains over existing methods. This study not only highlights the potential of LimTDD in quantum state preparation but also provides a robust theoretical and practical foundation for the future development of quantum computing technologies.

Figures

Figures reproduced from arXiv: 2507.14496 by the authors.

Figure 1
Figure 1. Example of a quantum circuit with Hadamard gates and [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. An example of Multiple-terminal ADD [21] and LimTDD representing [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. The quantum circuit that transfers the quantum state represented by the LimTDD shown in Fig. 2 to [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Experiment results of our method against ADD-based method [21]. [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]
Figure 5
Figure 5. Figure 5: Experiment results of our method against Qiskit [24] and QuICT [25]. [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

25 extracted references · 6 canonical work pages

  1. [21]

    Efficient deterministic preparation of quantum states using decision diagrams,

    F. Mozafari, G. De Micheli, and Y . Yang, “Efficient deterministic preparation of quantum states using decision diagrams,” Phys. Rev. A , vol. 106, p. 022617, Aug 2022. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.106.022617

    doi:10.1103/physreva.106.022617 2022

  2. [23]

    LimTDD: A Compact Decision Diagram Integrating Tensor and Local Invertible Map Representations,

    X. Hong, A. Dai, D. Gao, S. Li, Z. Ji, and M. Ying, “LimTDD: A Compact Decision Diagram Integrating Tensor and Local Invertible Map Representations,” Apr. 2025, arXiv:2504.01168 [cs]. [Online]. Available: http://arxiv.org/abs/2504.01168

    arXiv 2025

  3. [1]

    Algorithms for quantum computation: discrete logarithms and factoring,

    P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in In Proceedings 35th annual symposium on foundations of computer science , 1994, pp. 124–134

    1994

  4. [2]

    Prioritizing quantum computing use cases in the drug discovery and development pipeline,

    A. Kovyrshin, L. Tornberg, J. Crain, S. Mensa, I. Tavernelli, and A. Broo, “Prioritizing quantum computing use cases in the drug discovery and development pipeline,” Drug Discovery Today, vol. 30, p. 104323, 2025

    work page 2025

  5. [3]

    Quantum leap in material science,

    H. Gharibyan, “Quantum leap in material science,” Tech Briefs, March 2024. Fig. 4. Experiment results of our method against ADD-based method [21]. Fig. 5. Experiment results of our method against Qiskit [24] and QuICT [25]

    work page 2024

  6. [4]

    Combining quantum and ai for the next superpower,

    H. S. M. Gschwendtner and S. Zingg, “Combining quantum and ai for the next superpower,” in Nature Reviews Electrical Engineering , 1994, pp. 350–351

    work page 1994

  7. [5]

    Quantum speedups for stochastic optimiza- tion,

    A. Sidford and C. Zhang, “Quantum speedups for stochastic optimiza- tion,” in Proceedings of the 37th International Conference on Neural Information Processing Systems . NeurIPS, 2024, pp. 35 300–35 330

    work page 2024

  8. [6]

    An efficient algorithm for sparse quantum state preparation,

    N. Gleinig and T. Hoefler, “An efficient algorithm for sparse quantum state preparation,” in 2021 58th ACM/IEEE Design Automation Confer- ence (DAC). IEEE, 2021, pp. 433–438

    2021

Show all 25 references
  1. [7]

    Toward optimal circuit size for sparse quantum state preparation,

    R. Mao, G. Tian, and X. Sun, “Toward optimal circuit size for sparse quantum state preparation,” Physical Review A , vol. 110, no. 3, p. 032439, 2024

    2024

  2. [8]

    Simple quantum algorithm to efficiently prepare sparse states,

    D. Ramacciotti, A. I. Lefterovici, and A. F. Rotundo, “Simple quantum algorithm to efficiently prepare sparse states,” Phys. Rev. A , vol. 110, p. 032609, Sep 2024. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.110.032609

    2024 doi

  3. [9]

    Quantum-state preparation with universal gate decompositions,

    M. Plesch and C. Brukner, “Quantum-state preparation with universal gate decompositions,” Physical Review A, vol. 83, no. 3, p. 032302, Mar 2011

    2011

  4. [10]

    Synthesis of quantum-logic circuits,

    V . Shende, S. S. Bullock, S. S. Bullock, and I. L. Markov, “Synthesis of quantum-logic circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 2006

    2006

  5. [11]

    Quantum circuits for isometries,

    R. Iten, R. Colbeck, I. Kukuljan, J. Home, and M. Christandl, “Quantum circuits for isometries,” Physical Review A , Mar 2016. [Online]. Available: http://dx.doi.org/10.1103/physreva.93.032318

    2016 doi

  6. [12]

    Transformation of quantum states using uniformly controlled rotations,

    M. Mottonen, J. J. Vartiainen, V . Bergholm, and M. M. Salomaa, “Transformation of quantum states using uniformly controlled rotations,” arXiv preprint quant-ph/0407010 , 2004

    2004 arXiv

  7. [13]

    Quantum circuits with uniformly controlled one-qubit gates,

    V . Bergholm, J. J. Vartiainen, M. Mottonen, and M. M. Salomaa, “Quantum circuits with uniformly controlled one-qubit gates,” Physical Review A, vol. 71, no. 5, p. 052330, May 2005

    2005

  8. [14]

    Quantum state preparation with op- timal circuit depth: Implementations and applications,

    X.-M. Zhang, T. Li, and X. Yuan, “Quantum state preparation with op- timal circuit depth: Implementations and applications,” Physical Review Letters, vol. 129, no. 23, p. 230504, 2022

    2022

  9. [15]

    Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis,

    X. Sun, G. Tian, S. Yang, P. Yuan, and S. Zhang, “Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , vol. 42, no. 11, pp. 3301–3314, 2023

    2023

  10. [16]

    Bdd-based synthesis of reversible logic for large functions,

    R. Wille and R. Drechsler, “Bdd-based synthesis of reversible logic for large functions,” in 2009 46th ACM/IEEE Design Automation Confer- ence, 2009, pp. 270–275

    2009

  11. [17]

    Polynomial circuit verification using bdds,

    R. Drechsler, “Polynomial circuit verification using bdds,” in 2021 5th International Conference on Electrical, Electronics, Communication, Computer Technologies and Optimization Techniques (ICEECCOT) , 2021, pp. 49–52

    2021

  12. [18]

    QCEC: A JKQ tool for quantum circuit equivalence checking,

    L. Burgholzer and R. Wille, “QCEC: A JKQ tool for quantum circuit equivalence checking,” Software Impacts, vol. 7, p. 100051, 2021

    2021

  13. [19]

    Quantum circuit simulation with fast tensor decision diagram,

    Q. Zhang, M. Saligane, H.-S. Kim, D. Blaauw, G. Tzimpragos, and D. Sylvester, “Quantum circuit simulation with fast tensor decision diagram,” in 2024 25th International Symposium on Quality Electronic Design (ISQED), 2024, pp. 1–8

    2024

  14. [20]

    Automatic uniform quantum state preparation using decision diagrams,

    F. Mozafari, M. Soeken, H. Riener, and G. De Micheli, “Automatic uniform quantum state preparation using decision diagrams,” in 2020 IEEE 50th International Symposium on Multiple-Valued Logic (ISMVL) . IEEE, 2020

    2020

  15. [22]

    Quantum state preparation via free binary decision diagram,

    Y . Tanaka, H. Yamasaki, and M. Murao, “Quantum state preparation via free binary decision diagram,” 2024. [Online]. Available: https: //arxiv.org/abs/2407.01671

    2024 arXiv

  16. [24]

    Quantum computing with Qiskit,

    A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross, B. R. Johnson, and J. M. Gambetta, “Quantum computing with Qiskit,” 2024

    2024

  17. [25]

    QuICT: Quantum Computer of Institute of Computing Technology,

    Institute of Computing Technology, Chinese Academy of Sciences, “QuICT: Quantum Computer of Institute of Computing Technology,” https://quict-docs.readthedocs.io/aa/latest/, 2023

    2023

Pith tools

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