Pith. sign in

REVIEW 5 major objections 6 minor 15 references

Node Replacement based Approximate Quantum Simulation with Decision Diagrams

T0 review · 5 major / 6 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 Node replacement, in which low-contribution decision-diagram nodes are swapped for similar nodes found by locality-sensitive hashing, achieves a strong better-than-linear memory–fidelity trade-off for quantum-supremacy benchmark circuits…

desk verdict Genuine but modest advance over node-removal; headline resource claim overstates because replacement happens after construction. read the letter →

arxiv 2507.04335 v1 pith:IKSDGUWB submitted 2025-07-06 quant-ph cs.ET

Yexin Yan , Stefan Hillmich , Robert Wille , Christian Mayr This is my paper
classification quant-phcs.ET
keywords quantumcircuitsimulationdecisiondiagramsapproximatenodereplacementlocality-sensitivehashingsupremacybenchmarkmemory-fidelitytrade-off
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

Quantum-supremacy circuits have almost no redundancy, so decision diagrams that represent quantum states exactly need exponential memory, and approximating by deleting small-contribution nodes gives only a linear memory–fidelity trade-off at high depth. This paper proposes replacing those low-contribution nodes with other, similar nodes instead of deleting them, so the fidelity loss depends on node similarity as well as contribution. A locality-sensitive hashing scheme finds replacement candidates quickly, with 79x to 3064x speedups over exhaustive search. On quantum-supremacy benchmark circuits, the replacement approach shows a strong better-than-linear memory–fidelity trade-off even at high circuit depth, and the trade-off improves as circuit size grows. The method is presented as a post-construction compression of an already-built decision diagram.

What carries the argument

The machinery is node replacement inside a decision diagram, driven by the fidelity-loss identity $L = c_i(1 - \mathrm{Re}(v_i \cdot v'_i))$ for replacing a node with sub-vector $v_i$, contribution $c_i$, by a node with sub-vector $v'_i$; removal is the special case $v'_i = 0$ and loses $c_i$. To find $v'_i$ efficiently, the paper uses Super-Bit LSH, which hashes normalized sub-vectors into buckets using orthogonalized random projections; a hierarchical scheme sets the number of buckets from the level size so that each bucket has enough candidates. The replacement operation redirects a parent edge to the replacement node, with optional virtual edges when child structure must be preserved. The identity does the work: it converts approximation from a pure contribution-ranking problem into a similarity-search problem, which is where LSH enters.

What would settle it

Plot memory ratio versus fidelity for the 1x1 replacement strategy on a quantum-supremacy circuit at depth 15 or 20 and measure the log–log slope in the high-fidelity region: if the slope is approximately 1 throughout, the claimed strong better-than-linear trade-off at high depth is not present.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes that approximate simulation of quantum circuits with decision diagrams can be made much more memory-efficient for a fixed fidelity by reusing existing nodes rather than discarding them. The central quantity is the per-node fidelity loss $L_i = c_i(1 - \mathrm{Re}\langle v_i|v'_i\rangle)$, where $c_i$ is the norm contribution and $v'_i$ the sub-vector of the replacement node; replacing a node with a similar one makes the inner-product factor close to 1, so the loss is much smaller than removal's $c_i$. Four replacement strategies—single level, multiple level, independent level, and independent multiple level—are defined, with virtual edges used to preserve child information during independent replacement. Using Super-Bit LSH with hierarchical bucketing, the search for similar nodes is accelerated by orders of magnitude. The main reported result is that, for the quantum-supremacy benchmark at circuit depths 10 and higher, the memory–fidelity curve stays strongly better than linear, unlike the node-removal baseline whose curve becomes linear with depth.

Load-bearing premise

The practical value of the reported trade-off rests on the assumption that final decision-diagram size is the resource that matters; the paper states that replacement is applied after the diagram is built, when peak memory has already been reached, so the method as presented cannot simulate more qubits within the same memory budget.

Editorial extensions

If this is right

  • For the same fidelity budget, a decision diagram built with node replacement can be much smaller than one built with node removal, with the gap widening as circuit size grows.
  • The strategy family (1x1, Nx1, 1xX, NxX) lets a user choose a point on the memory–fidelity curve: single-level for very high fidelity, multi-level for deep memory cuts, independent levels to slow fidelity loss, and hybrid for intermediate regions.
  • LSH-based node search removes the quadratic exhaustive-search bottleneck, making the replacement step practical for decision diagrams with hundreds of thousands of nodes.
  • High circuit depth no longer forces the trade-off toward linear, because fidelity loss is governed by node similarity rather than only by a flattened contribution distribution.

Reading between the lines

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

  • The similarity-based fidelity-loss identity suggests that any representation with reusable sub-vectors could use the same replacement trick; tensor networks and other compressed state representations might benefit from replacing near-identical tensors rather than truncating them.
  • The method's performance should improve with circuit size because the density of nodes in the fixed vector space grows, making similar sub-vectors easier to find; the paper assumes this trend but cannot test larger circuits with available resources.
  • If LSH bucket membership were maintained during decision-diagram construction, replacement could be applied incrementally and potentially shift the memory bottleneck from construction to a tunable approximation budget; the paper only sketches this as future work.
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

5 major / 6 minor

Summary. The paper proposes an approximate simulation method for quantum circuits represented as decision diagrams (DDs). Instead of deleting low-contribution nodes as in prior work [11], it redirects their parent edges to similar higher-contribution nodes, choosing replacements by maximizing the real part of the complex inner product of normalized sub-vectors, and accelerates the search with Super-Bit locality-sensitive hashing. Four replacement strategies are introduced (single-level 1x1, multiple-level Nx1, independent 1xX, and independent multiple-level NxX). On quantum supremacy benchmark instances (4x4 and 4x5 qubits, depths 10, 15, and 20), the reported memory-fidelity curves show better-than-linear behavior and improvement over the node-removal baseline at high depths, with LSH speeding up the replacement search by 79x to 3064x. The paper explicitly notes that replacement is performed after the DD is fully constructed, so the peak memory during construction is not reduced.

Significance. If the claims are correct, the work is a useful step: it shows that the final size of a DD can be reduced more per unit fidelity loss than by node removal, and the LSH acceleration makes the replacement search practical. The paper is honest about the post-construction limitation in the Discussion, and the comparison to [11] on the same benchmarks is a strength. However, the headline 'resource requirement' claim is not supported for end-to-end simulation because peak memory occurs during construction, and the central fidelity-loss formula for multiple replacements is asserted without a valid proof. The empirical base is also narrow: each benchmark is represented by a single random instance and no variance is reported. With scoped claims and additional evidence, the contribution would be publishable.

major comments (5)
  1. [Abstract and Section III] The resource-reduction claim is overstated relative to what the method delivers. Section III states that node replacement is done after the DD is constructed and that the maximum memory requirement occurs during construction; consequently, the method cannot increase the number of qubits that can be simulated within the same resources. All reported memory ratios in Tables II and III and Figures 2-7 compare the post-replacement DD size with the exact post-construction DD size, not the end-to-end memory peak. The abstract's phrase 'drastically reducing the resource requirement' should be revised to specify that the reduction applies to the final DD representation size, and the peak-memory limitation should be acknowledged in the abstract and introduction.
  2. [Section IV-C, Eq. (10)] The claim that replacing n nodes yields fidelity F = |1 - sum_i L_fid,i|^2 is not proved and is not generally true when replacements occur on different levels. A path through the DD can pass through several replaced nodes, so the inner product contains cross terms between the corresponding overlaps; for example, two replacements with norm contributions c1 and c2 and overlaps p1 and p2 contribute c1*c2*(p1*p2 - 1) in addition to c1*(1-p1) + c2*(1-p2). The formula is exact only for replacements on a single level, where the affected amplitudes are disjoint. Since strategies 1xX and NxX replace nodes on different levels, either a proof restricted to the actual replacement operations, or an explicit statement that Eq. (10) is per-level and that total fidelity is computed exactly, is needed.
  3. [Section IV-I] The replacement criterion maximizes the real part of the complex inner product, and the paper states without supporting data that 'the imaginary part becomes negligibly small.' Because the reported fidelity is |<psi|phi>|^2, an unquantified imaginary part could make the selected replacement suboptimal or make the fidelity-loss definition in Eq. (9) misleading. Please either prove a bound on the imaginary part (for example, using the normalization of sub-vectors and the selection rule) or report the distribution of imaginary parts for the benchmarks used in Figures 2-7.
  4. [Section II, Figures 2-7 and Tables II-III] All benchmark results are for one named instance per size and depth (for example, inst4x4_10_0 and inst4x5_10_0), and no error bars or standard deviations are reported. Random quantum circuits vary from instance to instance, so the 'for the first time' claim and the scaling conclusions are not statistically supported. Please present results over several random circuit instances, or at least state the single-instance limitation and report seed-to-seed variation.
  5. [Table I and abstract] The reported speed-up is for the replacement-search phase only, not for the total simulation time. The abstract claims 'minimal run time overhead,' but the paper does not report end-to-end run times including DD construction, which is the dominant cost for the benchmarks considered. Without end-to-end timings, the run-time overhead claim is unsupported.
minor comments (6)
  1. [Throughout] There are several typographical issues: 'constrution' in Section III, 'F oundations' in reference [2], inconsistent capitalization of 'Sota'/'SOTA', and inconsistent spacing in benchmark names such as 'inst4x4 10 0'.
  2. [Reference [10]] Reference [10] is listed as 'arxiv (not yet submitted)' and should be updated to its final published form or removed if it remains unpublished.
  3. [Figure 2] The caption states that the curves are obtained with a Savitzky-Golay filter, but the raw data points are sparse and the filter can introduce artifacts near the endpoints; the authors should clarify whether any conclusions depend on the filtering.
  4. [Section IV-H] The selection of the norm-contribution threshold is described only as 'determine a threshold,' without a sensitivity analysis; some discussion of how the threshold choice affects the trade-off curves would be helpful.
  5. [Equations (7)-(9)] The notation in Eqs. (7)-(9), especially 'w10w'*10' and 'v_i v'_i*', should be defined explicitly as inner products with complex conjugation to avoid ambiguity.
  6. [Throughout] No code or data availability statement is included; given that the central claims are empirical, providing the benchmark instances and the implementation would strengthen reproducibility.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the better-than-linear memory-fidelity trade-off is an empirical sweep result, not an identity or a fitted prediction.

full rationale

The paper's central claim is an experimentally measured Pareto frontier: for a fixed circuit, the fraction of nodes moved from the replacement list to the replaced list sets the memory ratio, and the fidelity of the resulting approximate decision diagram is then evaluated. This is a parameter sweep, not a prediction forced by construction. The fidelity is the standard full-state inner-product fidelity; although the node-selection heuristic maximizes the real part of sub-vector inner products (Eq. 9), the reported fidelity is not defined to be that heuristic. The LSH component is validated against exhaustive search by RMSE and runtime, so it is an approximation to an independent baseline rather than a renaming. The only prior self-citation with author overlap, [11], supplies the norm-contribution definition and the previous SOTA baseline; it is a separate published result and is not invoked as a uniqueness theorem or as a substitute for the present measurements. The Discussion's admission that node replacement occurs after DD construction and therefore does not reduce peak memory is a scope limitation on the resource claim, not a circular step. No fitted constants are used to obtain the better-than-linear behavior, and no equation in the paper reduces to its own input.

Assumptions & free parameters 3 free parameters · 4 assumptions · 1 invented entities

The central claim depends on design choices and empirical assumptions rather than on new physical axioms. The main free parameters are the contribution threshold, the LSH batch size, and the hierarchical LSH parameters. The derivations assume DD subvector normalization, an approximately real inner product, a specific node distribution across DD levels, and the LSH bucket-similarity premise. Virtual edges are a new data-structure construct with quantified overhead but no independent validation.

free parameters (3)
  • contribution threshold = swept along the trade-off curve
    Nodes are ranked by norm contribution and split into replaced and replacement lists by a threshold; sweeping this threshold produces the memory-fidelity curves. It is a control parameter, not a fitted physical constant.
  • lshn = 2
    Number of orthogonalized random projection vectors per LSH batch; chosen by hand to correspond to the real and imaginary parts of a state vector entry (Methods IV-J).
  • hierarchical LSH parameters = lshl starts at (log2 N)/2; split buckets when size exceeds sqrt(N)
    Adaptive scheme avoids manual tuning for different DD levels and benchmark sizes; affects speed and quality of replacement search (Methods IV-K).
assumptions (4)
  • domain assumption Each decision-diagram node's subvector is normalized to unit norm.
    Invoked in the fidelity-loss derivation in Section IV-C, citing reference [12]. Without this, the formula L_fid = c_i(1 - inner product) does not follow.
  • ad hoc to paper The imaginary part of the inner product between a replaced node and its replacement is negligibly small.
    Section IV-I states this is found experimentally, but no proof or systematic error analysis is provided. It is used to justify treating the fidelity loss as a real quantity and to equate maximizing cosine similarity with maximizing fidelity.
  • domain assumption For the quantum supremacy circuits, nodes are distributed across DD levels roughly as 50% at level 0, 25% at level 1, and so on.
    Used to compute the memory overhead of virtual edges, yielding the 22% and 5.5% saturation bounds in Sections IV-F and IV-G. The assumption may not hold universally.
  • domain assumption Nodes hashed into the same LSH bucket are more similar to each other than nodes from different buckets.
    This is the basis of the LSH approximation in Section IV-H, which restricts replacement candidates to the same bucket. It is a standard locality-sensitive-hashing premise but is not verified for the specific DD node distributions.
invented entities (1)
  • virtual edge with virtual edge number
    purpose: Preserves child-node information when a parent edge is redirected during independent node replacement, allowing replacement on multiple levels without bundling the entire subtree.
    This is a data-structure construct specific to the method. Its memory cost is quantified (0.33M on level 1, 0.55M on level 2 and above per virtual edge), but it has no independent validation outside the paper and is not observable through any external falsifiable prediction.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Node Replacement based Approximate Quantum Simulation with Decision Diagrams." pith.science (2026). https://pith.science/paper/IKSDGUWB

@misc{pith2026250704335,
  author       = {Pith},
  title        = {Pith review of: Node Replacement based Approximate Quantum Simulation with Decision Diagrams},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IKSDGUWB}},
  note         = {Machine review of arXiv:2507.04335}
}
read the original abstract

Simulating a quantum circuit with a classical computer requires exponentially growing resources. Decision diagrams exploit the redundancies in quantum circuit representation to efficiently represent and simulate quantum circuits. But for complicated quantum circuits like the quantum supremacy benchmark, there is almost no redundancy to exploit. Therefore, it often makes sense to do a trade-off between simulation accuracy and memory requirement. Previous work on approximate simulation with decision diagrams exploits this trade-off by removing less important nodes. In this work, instead of removing these nodes, we try to find similar nodes to replace them, effectively slowing down the fidelity loss when reducing the memory. In addition, we adopt Locality Sensitive Hashing (LSH) to drastically reduce the computational complexity for searching for replacement nodes. Our new approach achieves a better memory-accuracy trade-off for representing a quantum circuit with decision diagrams with minimal run time overhead. Notably, our approach shows good scaling properties when increasing the circuit size and depth. For the first time, a strong better-than-linear trade-off between memory and fidelity is demonstrated for a decision diagram based quantum simulation when representing the quantum supremacy benchmark circuits at high circuit depths, showing the potential of drastically reducing the resource requirement for approximate simulation of the quantum supremacy benchmarks on a classical computer.

Figures

Figures reproduced from arXiv: 2507.04335 by the authors.

Figure 1
Figure 1. Memory ratio vs. fidelity for exhaustive search [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Single level node replacement (1x1), multiple level [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. The saturation point of memory reduction converges [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (9 more)
Figure 5
Figure 5. Figure 5: The saturation point of memory reduction converges [PITH_FULL_IMAGE:figures/full_fig_p005_5.png]
Figure 8
Figure 8. Figure 8: Quantum state with vector (left) and DD (right) [PITH_FULL_IMAGE:figures/full_fig_p006_8.png]
Figure 7
Figure 7. Figure 7: Memory ratio vs. fidelity when increasing circuit depth. [PITH_FULL_IMAGE:figures/full_fig_p006_7.png]
Figure 9
Figure 9. Figure 9: fid loss path. In a DD, the weight of an edge is denoted beside the edge. When no weight is denoted, the weight is 1. The weights of the two child edges of a node are normalized, so that the norm of the vector of the two weights is 1 [12]. By sharing the nodes, DDs can…
Figure 10
Figure 10. Figure 10: Single level node replacement. The red cross indicates [PITH_FULL_IMAGE:figures/full_fig_p008_10.png]
Figure 11
Figure 11. Figure 11: Multiple level node replacement. The red cross [PITH_FULL_IMAGE:figures/full_fig_p009_11.png]
Figure 12
Figure 12. Figure 12: Independent node replacement. A node in the left [PITH_FULL_IMAGE:figures/full_fig_p009_12.png]
Figure 13
Figure 13. Figure 13: Independent node replacement. In this example, first, when replacing nodes on level 1, the node q1.3 is replaced by [PITH_FULL_IMAGE:figures/full_fig_p010_13.png]
Figure 14
Figure 14. Figure 14: Independent multiple level node replacement. In this example, nodes of 2 levels (level 2 and 3) are replaced together. [PITH_FULL_IMAGE:figures/full_fig_p010_14.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

15 extracted references · 7 canonical work pages

  1. [11]

    Approximating decision diagrams for quantum circuit simulation,

    S. Hillmich, A. Zulehner, R. Kueng, I. L. Markov, and R. Wille, “Approximating decision diagrams for quantum circuit simulation,” ACM Transactions on Quantum Computing , vol. 3, no. 4, jul 2022. [Online]. Available: https://doi.org/10.1145/3530776

    doi:10.1145/3530776 2022

  2. [1]

    A fast quantum mechanical algorithm for database search,

    L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing , ser. STOC ’96. New York, NY , USA: Association for Computing Machinery, 1996, p. 212-219. [Online]. Available: https://doi.org/10.1145/237814.237866

    arXiv 1996

  3. [2]

    Algorithms for quantum computation: discrete logarithms and factoring,

    P. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in Proceedings 35th Annual Symposium on F oundations of Computer Science , 1994, pp. 124–134

    work page 1994

  4. [3]

    M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition . Cambridge University Press, 2010

    2010

  5. [4]

    Quantum computational supremacy,

    A. W. Harrow and A. Montanaro, “Quantum computational supremacy,” Nature, vol. 549, no. 7671, pp. 203–209, Sep 2017. [Online]. Available: https://doi.org/10.1038/nature23458

    doi:10.1038/nature23458 2017

  6. [5]

    Characterizing quantum supremacy in near-term devices,

    S. Boixo, S. V . Isakov, V . N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, “Characterizing quantum supremacy in near-term devices,” Nature Physics , vol. 14, no. 6, pp. 595–600, Jun 2018. [Online]. Available: https://doi.org/10. 1038/s41567-018-0124-x

    work page 2018

  7. [6]

    A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware,

    B. Villalonga, S. Boixo, B. Nelson, C. Henze, E. Rieffel, R. Biswas, and S. Mandr `a, “A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware,” npj Quantum Information , vol. 5, no. 1, p. 86, Oct 2019. [Online]. Available: https://doi.org/10.1038/s41534-019-0196-1

    doi:10.1038/s41534-019-0196-1 2019

  8. [7]

    Simulating quantum computation by contracting tensor networks,

    I. L. Markov and Y . Shi, “Simulating quantum computation by contracting tensor networks,” SIAM Journal on Computing , vol. 38, no. 3, pp. 963–981, 2008. [Online]. Available: https: //doi.org/10.1137/050644756

    doi:10.1137/050644756 2008

Show all 15 references
  1. [8]

    Qmdds: Efficient quantum function representation and manipulation,

    P. Niemann, R. Wille, D. M. Miller, M. A. Thornton, and R. Drechsler, “Qmdds: Efficient quantum function representation and manipulation,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , vol. 35, no. 1, pp. 86–99, 2016

    2016

  2. [9]

    Advanced simulation of quantum compu- tations,

    A. Zulehner and R. Wille, “Advanced simulation of quantum compu- tations,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , vol. 38, no. 5, pp. 848–859, 2019

    2019

  3. [10]

    Quantum supremacy is both closer and farther than it appears,

    I. Markov, A. Fatima, S. Isakov, and S. Boixo, “Quantum supremacy is both closer and farther than it appears,” arxiv (not yet submitted) ,

  4. [12]

    Just like the real thing: fast weak simulation of quantum computation,

    S. Hillmich, I. L. Markov, and R. Wille, “Just like the real thing: fast weak simulation of quantum computation,” in Proceedings of the 57th ACM/EDAC/IEEE Design Automation Conference, ser. DAC ’20. IEEE Press, 2020

    2020

  5. [13]

    Super-bit locality-sensitive hashing,

    J. Ji, J. Li, S. Yan, B. Zhang, and Q. Tian, “Super-bit locality-sensitive hashing,” in Advances in Neural Information Processing Systems , F. Pereira, C. Burges, L. Bottou, and K. Weinberger, Eds., vol. 25. Curran Associates, Inc., 2012. [Online]. Available: https://proceedin...

    2012

  6. [14]

    Similarity estimation techniques from rounding algorithms,

    M. S. Charikar, “Similarity estimation techniques from rounding algorithms,” in Proceedings of the Thiry-F ourth Annual ACM Symposium on Theory of Computing , ser. STOC ’02. New York, NY , USA: Association for Computing Machinery, 2002, p. 380-388. [Online]. Available: https:/...

    2002

  7. [2018]

    Available: https://arxiv.org/abs/1807.10749

    [Online]. Available: https://arxiv.org/abs/1807.10749

    arXiv

Pith tools

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