Pith. sign in

REVIEW 5 major objections 6 minor 65 references

A Constant Measurement Quantum Algorithm for Graph Connectivity

T0 review · 5 major / 6 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 argues that graph connectedness can be decided with two quantum measurements, because non-unitary ZX-calculus gates placed on edges fuse into one GHZ state per connected component.

desk verdict The ZX-spider construction is sound as a postselected projection, but the constant-measurement claim relies on an unproven ancilla gadget and the failure statistics are wrong. read the letter →

arxiv 2411.15015 v2 pith:EFITO3ZZ submitted 2024-11-22 quant-ph

Maximilian Balthasar Mansky , Chonfai Kam , Claudia Linnhoff-Popien This is my paper · ORCID
classification quant-ph MSC 81P6805C4068R10 PACS 03.67.Lx
keywords graphconnectivityquantumalgorithmZXcalculusnon-unitarygatesGHZstatesconstantmeasurementcomplexityconnectedcomponentsstatedecay
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 proposes a quantum algorithm that decides whether an undirected graph is connected using a constant number of measurements: two measurements of all qubits, regardless of how many nodes or edges the graph has. The construction maps each node to a qubit and each edge to a non-unitary two-qubit gate from ZX calculus; the fusion rule of these gates contracts all edges inside a connected component into a single projective gate, placing that component into a GHZ state. Each connected component then appears as a block of qubits whose measurement outcomes are perfectly correlated, so two measurement rounds distinguish one block from more than one block with success probability $3/4$. The same machinery identifies the individual connected components with a number of measurements proportional to the number of components. The paper is open about a cost: the projective gates dissipate state amplitude, and the ancilla-based remedy that would make the O(1) claim clean is stated as an open question.

What carries the argument

The load-bearing object is the Z spider of ZX calculus: a multi-legged non-unitary tensor whose matrix has value $1$ in the top-left entry, $e^{i\alpha}$ in the bottom-right entry, and zeros elsewhere; as a map it is a projector onto the two-dimensional subspace spanned by $|0\cdots0\rangle$ and $|1\cdots1\rangle$. Its contraction rule lets two same-colour spiders that share a wire fuse into a single spider whose phase is the sum of the two phases, so the entire edge set of a connected component collapses to one spider on that component's qubits. Because the spider gates are abelian and nilpotent, repeated edges and self-loops leave the contraction unchanged, which is what lets the algorithm accept multigraphs and graphs with loops. This contraction is what turns the unordered list of edges into a global statement about the graph without ever sorting the edges.

What would settle it

Implement each two-qubit Z spider as a concrete unitary circuit with ancilla qubits, for instance via the Bell-measurement replacement shown in the paper, run the full algorithm on a graph with $n$ nodes, and estimate the probability that the output state is the intended tensor product of GHZ states. If that probability decays exponentially in $n$ or in the number of edges, or if a constant success probability requires the number of ancillas to grow with $n$, then the claimed O(1) measurement count is not achieved by that implementation.

Watch

Extended reading notes

Core claim

The paper's central claim is that the connectedness of an undirected graph can be encoded as a product of GHZ states by a contractible set of non-unitary gates. For an edge $\{n_i,n_j\}$ the algorithm applies a two-qubit Z spider, whose matrix has a single $1$ in the first entry and a single $e^{i\alpha}$ in the last entry and zeros elsewhere; the ZX fusion rule then contracts every connected cluster of edge-spiders into one spider touching the qubits of that cluster. Each cluster spider projects the cluster into the subspace $\mathrm{span}\{|0\cdots0\rangle, e^{i\alpha}|1\cdots1\rangle\}$, i.e. into a GHZ state. The final state is $\bigotimes_k |\mathrm{GHZ}\rangle_k$ over the connected components, and because each GHZ block measures independently as all-zero or all-one, two simultaneous measurements of all qubits decide connectedness with success probability $3/4$. The paper further claims that successive measurement rounds, combined with the XOR operation, reveal the partition into connected components in $O(|G_k|)$ measurements.

Load-bearing premise

The algorithm's O(1)-measurement claim rests on the assumption that the non-unitary spider gates can be implemented with ancilla qubits without losing the state amplitude; the paper states that the number of ancillas needed to prevent state decay is an open question and does not prove that the ancilla version succeeds deterministically.

Editorial extensions

If this is right

  • Graph connectedness becomes a constant-measurement decision problem: two shots of the prepared state determine, with probability $3/4$, whether the graph has one component or several, independent of the node and edge counts.
  • Connected components can be recovered by repeated measurements: a number of all-qubit measurement rounds of order $O(|G_k|)$, combined by XOR, classifies qubits into their GHZ blocks.
  • The algorithm applies to every undirected graph, including graphs with repeated edges and self-loops, because the Z-spider gates are abelian and nilpotent.
  • The circuit depth is bounded between $O(\lceil m/n \rceil)$ and $O(m)$ when edge gates on disjoint nodes are parallelized, with an average-case upper bound derived from integer partitions.
  • Without ancillas the algorithm needs $O(2^n)$ measurement calls because of state decay; with ancillas the paper claims the call count drops to $O(1)$ at a total cost of $O(n+m)$ qubits.

Reading between the lines

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

  • If the ancilla construction is made explicit and shown to preserve amplitude, this would give a graph decision algorithm whose measurement count is independent of graph size; the paper's own open question about the ancilla count means the practical constant-time claim is conditional.
  • The same spider-contraction route could be tried for other global graph properties that are partition-like, such as bipartiteness or strong connectivity, by choosing projective gates whose fixed states encode those properties; the paper's discussion points in this direction.
  • The state-decay problem may be unavoidable rather than technical: any unitary implementation of a projector has success probability equal to the input's overlap with the target subspace, so the constant-call claim may end up moving the exponential cost into ancilla count or gate depth instead of measurement count.
  • A direct testable extension is to run the algorithm on current hardware using the Bell-measurement GHZ construction from the paper and compare the block-correlation pattern of the measured shots with the true connected components of random graphs; the paper's simulation ignores decay, so hardware data would probe exactly the missing assumption.
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 a quantum algorithm for undirected graph connectivity that encodes each edge as a two-qubit Z-spider (a non-unitary projector) and relies on the ZX-calculus fusion rule to argue that every connected component becomes a multi-qubit GHZ state. The authors claim that two measurements suffice to decide connectivity in constant time O(1), that connected components can be found with a linear number of measurements, and that the circuit depth is bounded above and below by graph-dependent expressions. They acknowledge a 'state decay' caused by the non-unitary gates, propose ancilla qubits as a remedy, and provide a Julia/Yao simulation notebook.

Significance. The central idea of using abelian idempotent projectors from ZX calculus to merge graph edges into a collective GHZ-like condition is original and, as a purely algebraic construction, is elegant. The paper is also unusually honest about the main obstacle: without ancillas the algorithm requires exponentially many runs. If a deterministic ancilla implementation with O(1) acceptance probability existed, the constant-measurement claim would be remarkable. However, no such implementation is derived, and the argument as it stands leaves the main claim unsupported. Strengths of the manuscript include a self-contained derivation of the projector-fusion mechanism, an explicit numerical notebook for the ideal postselected behavior, and a clear identification of the state-decay problem, even though the proposed solution is only sketched.

major comments (5)
  1. [IV.D and Table II] The constant-measurement claim is unsupported because the ancilla remedy is not derived. Section IV.D states that 'How many ancilla qubits are necessary to avoid a state decay is left as an open question' and then asserts a trade-off between O(2^n) calls without ancillas and O(1) calls with m ancillas. A Z-spider is a rank-2 projector, and from the initial state |+^n> the postselected subspace for k connected components has dimension 2^k, so the acceptance probability of the full sequence is 2^{k-n}. Any unitary-plus-measurement implementation of the same projectors has the same acceptance probability unless the rejected branches are coherently recovered, and the manuscript provides no mechanism or calculation for such recovery. The O(1) row in Table II is therefore an assumption, not a result.
  2. [IV.B.1, Eq. (8a)] The failure probability formula for disconnected graphs is incorrect for k>2. In the ideal postselected state, the k connected component states are independent fair bits, so in a single measurement the probability that all fragments give the same outcome is 2/2^k = 2^{1-k}, not 1/k as written in Eq. (8a). Over M measurements the failure probability is (2^{1-k})^M, not 1/k^M. For example, with k=3 and M=2, Eq. (8a) gives an error of 1/9, whereas the actual error is 1/16. This does not rescue the constant-measurement claim, since the dominant issue is the exponentially small state-preparation probability, but the statistical analysis as written is wrong.
  3. [III.C and Discussion] The statement that the non-unitary spider gates can be executed with certainty on the states used in the algorithm is incorrect. Equation (3) shows that a Z-spider has success probability 1 only when its input is already GHZ-like. In the algorithm, the first edge gate acts on |++...> after Hadamards on |0^n>, and the acceptance probability of that single gate is 1/2; the product over all edges is exponentially small. The Discussion's claim that 'the operation can be executed with certainty' contradicts the state-decay analysis in Section IV.D and should be removed or carefully qualified.
  4. [IV.C, Eq. (14), and Appendix B.2] The claimed depth lower bound is not a proven bound. The text introduces it as 'The best experimental fit is one of the form ...' and adds that 'This fit still underestimates the behavior for large n but provides a reasonable lower bound.' A numerical fit with fitted exponent 0.88 and prefactor 2 is not a mathematical lower bound. The depth analysis should clearly distinguish rigorously proven upper bounds from empirical estimates, otherwise the paper's depth contribution is overstated.
  5. [Appendix A] The numerical simulation cannot validate the algorithm's success probability because it 'ignores state decay' and samples from the remaining state after the projectors. This is equivalent to sampling from the ideal postselected state, not from the physical measurement statistics of the non-unitary circuit. The notebook may be useful for checking the algebraic fusion and the ideal measurement patterns, but it does not provide evidence for the feasibility of the constant-measurement claim, which is precisely about the probability of reaching that postselected state.
minor comments (6)
  1. [Section II] The text calls the edge gate 'nilpotent, N^2 = N'; an operator satisfying N^2 = N is idempotent, not nilpotent. The property that repeated edges do not cancel is idempotence, and the terminology should be corrected.
  2. [IV.B.2] The number of measurements for connected components is stated as M = 2|G_k| and described as 'sublinear time.' Since |G_k| can be as large as n, this is linear in the number of nodes, not sublinear; the abstract's 'linear number of measurements' is the correct characterization.
  3. [Figure 6 and IV.D] Figure 6 is under-specified: the MX measurement basis is not defined, the way the circuit implements the Z-spider projector is only sketched, and the success probability of the shown translation is never computed. A concrete circuit and its acceptance probability are needed before the ancilla remedy can be assessed.
  4. [Appendix B.1] The general formula N(n',\lambda)=\binom{n'+1}{2\lambda} is asserted after deriving only the \lambda=2 case. A proof for all \lambda, or a citation to a source for the closed form, is needed to make the upper-bound derivation rigorous.
  5. [Table II] The row labeled 'Time \times space' is not a standard complexity measure; the product of the number of measurements and the number of qubits has no clear operational meaning and should either be defined or removed.
  6. [Introduction and IV.A] The claimed generality to graphs with self-loops is not supported by the construction: a two-qubit Z-spider requires two distinct wires, and the mapping of a self-loop to such a gate is not described.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the GHZ-state encoding follows from the stated projector construction, and the unsupported ancilla claim is a correctness concern, not a definitional reduction.

full rationale

The derivation chain is self-contained in the sense relevant to circularity. The central construction maps each graph edge to a fixed two-qubit Z-spider projector; the fusion rule of ZX calculus is an external, standard mathematical result, not an author-specific or fitted input. The final state being a tensor product of GHZ states over connected components follows from the projector algebra, and the measurement analysis in Eqs. (8)-(9) is a direct probability calculation on that state. No fitted parameter is renamed as a prediction: the only fit in the paper, the empirical depth lower bound O(2m/(1+0.5n)^0.88) in Appendix B.2, is explicitly labeled 'best experimental fit' and is not used as evidence for the constant-measurement claim. The ancilla-based O(1) claim in Sec. IV.D is unsupported — the paper itself says 'How many ancilla qubits are necessary to avoid a state decay is left as an open question' — but a missing proof or internal inconsistency is a correctness risk, not circularity. There are no load-bearing self-citations; the non-unitary-implementation citation [41] is external. Therefore no step reduces to its own input by construction, and the circularity score is 0.

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

The central claim rests on the physical implementability of non-unitary projectors and on the unsupported ancilla remedy; the depth analysis includes fitted parameters.

free parameters (2)
  • depth fit exponent = 0.88
    Empirical exponent in the lower bound O(2m/(1+0.5n)^0.88) fitted to numerical simulations in Appendix B.2.
  • depth fit constant = 0.5
    Empirical constant in the same fitted lower bound.
assumptions (4)
  • domain assumption Non-unitary Z spiders act as projectors onto the span{|0...0>, |1...1>} subspace and can be applied to quantum states.
    Section III.C defines the spider as a projector; the algorithm assumes such non-unitary operations are physically implementable with the stated postselection probabilities.
  • standard math The ZX-calculus fusion rule holds for these non-unitary spiders, so the product of two-qubit spiders for a connected component equals a single large spider.
    Section IV.A uses the fusion rule from ZX-calculus; this is a known mathematical property of the spider tensors.
  • ad hoc to paper The ancilla-based implementation of the spider preserves the state without decay and succeeds with O(1) repetitions.
    Section IV.D asserts the trade-off O(2^n) calls without ancillas or O(1) calls with m ancillas, but gives no proof and leaves the number of ancillas open.
  • domain assumption Edges can be applied in any order because the spiders are abelian (commuting) projectors.
    Section II argues that the edge list is unsorted, so gates must be abelian; the algorithm relies on commutativity of the projectors.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Constant Measurement Quantum Algorithm for Graph Connectivity." pith.science (2026). https://pith.science/paper/EFITO3ZZ

@misc{pith2026241115015,
  author       = {Pith},
  title        = {Pith review of: A Constant Measurement Quantum Algorithm for Graph Connectivity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EFITO3ZZ}},
  note         = {Machine review of arXiv:2411.15015}
}
read the original abstract

We introduce a novel quantum algorithm for determining graph connectedness using a constant number of measurements. The algorithm can be extended to find connected components with a linear number of measurements. It relies on non-unitary abelian gates taken from ZX calculus. Due to the fusion rule, the two-qubit gates correspond to a large single action on the qubits. The algorithm is general and can handle any undirected graph, including those with repeated edges and self-loops. The depth of the algorithm is variable, depending on the graph, and we derive upper and lower bounds. The algorithm exhibits a state decay that can be remedied with ancilla qubits. We provide a numerical simulation of the algorithm.

Figures

Figures reproduced from arXiv: 2411.15015 by the authors.

Figure 1
Figure 1. The main elements of ZX calculus are the spiders. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. The ingredients of ZX calculus relevant to this work. [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. figure 3. For parallel operations, the corresponding ma [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: The general matrix representation of a multi-legged [PITH_FULL_IMAGE:figures/full_fig_p003_4.png]
Figure 5
Figure 5. Figure 5: Illustration of the graph component algorithm for a two-piece graph. It shows from left to right the transformation [PITH_FULL_IMAGE:figures/full_fig_p005_5.png]
Figure 6
Figure 6. Figure 6: A possible translation from the non-unitary spider [PITH_FULL_IMAGE:figures/full_fig_p006_6.png]
Figure 7
Figure 7. Figure 7: The Young diagrams used to calculate the example [PITH_FULL_IMAGE:figures/full_fig_p010_7.png]
Figure 8
Figure 8. Figure 8: Histogram of the distribution of depths in the quan [PITH_FULL_IMAGE:figures/full_fig_p010_8.png]
Figure 9
Figure 9. Figure 9: The depth of the circuit as the probability of an [PITH_FULL_IMAGE:figures/full_fig_p011_9.png]
Figure 10
Figure 10. Figure 10: As the number of nodes increases, the average [PITH_FULL_IMAGE:figures/full_fig_p012_10.png]
Figure 11
Figure 11. Figure 11: Visual explanation of the graph stacking as dis [PITH_FULL_IMAGE:figures/full_fig_p012_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

65 extracted references · 58 canonical work pages

  1. [1]

    The result- ing state can be measured

    Graph connectedness After the application of the algorithm, the state is of the form |0n⟩ → O k |GHZ⟩k (7) with k components over the n qubits corresponding to connected components of the respective size. The result- ing state can be measured. Each state fragment corre- sponding to a connected component is independent from each other and can be individual...

    work page

  2. [2]

    F¨ orderprogramm Quanten- technologien – von den Grundlagen zum Markt

    Connected components The algorithm can be extended to identify connected components as well, in O(|Gk|) steps. Each group of qubits corresponding to a connected component are al- ways in the same measured state. As they are indepen- dent of each other, it is possible to identify them based on their coordinated measurement results and therefore the connect...

    work page

  3. [3]

    We can introduce a matrix with d rows and n′ ≡ n − 1 columns, where each element is either 0 or 1

    Upper bound as an integer partition problem To derive an analytical upper bound on the depth of the quantum circuit, the original problem can be refor- mulated as a combinatorial problem. We can introduce a matrix with d rows and n′ ≡ n − 1 columns, where each element is either 0 or 1. The objective is to compute the connected components of 1s within each...

    work page

  4. [4]

    This is equivalent to counting the number of ways to select 3 elements from sets of size n′

    Interestingly, the sum of binomial coefficients might have a combinatorial Interpretation: the sum of these binomial coefficients is essentially counting the number of ways to select 2 elements from sets of sizen′ −1, n′ −2, · · ·, 1. This is equivalent to counting the number of ways to select 3 elements from sets of size n′. From equation (B6), one can i...

    work page

  5. [5]

    Hence, the first Young diagram does not contribute. 10 λ = (1, 1, 1, 1, 1, 1, 1, 1, 1, 1) λ = (2, 1, 1, 1, 1, 1, 1, 1, 1) λ = (3, 1, 1, 1, 1, 1, 1, 1) λ = (2, 2, 1, 1, 1, 1, 1, 1) λ = (2, 2, 2, 1, 1, 1, 1) λ = (2, 2, 2, 2, 1, 1) λ = (2, 2, 2, 2, 2) Figure 7. The Young diagrams used to calculate the example of n = 5 and m = 10. Counting the second Young di...

    work page

  6. [6]

    For simple graphs, the standard graph analysis packages can be used to generate random Erd˝ os-R´ enyi graphs [59], which can then be assigned to the nodes

    Numerical approximation A numerical approach is straightforward. For simple graphs, the standard graph analysis packages can be used to generate random Erd˝ os-R´ enyi graphs [59], which can then be assigned to the nodes. Erd˝ os-R´ enyi graphs have a probability of connectivity, where is each edge is either connected or not based on this probability. Man...

    work page

  7. [7]

    This is explained vi- sually in figure 11 for a fraction of a complete graph

    Sorted graphs For sorted graphs, the upper bound in depth with no repeated edges and no self-loops is O(2n), due to the edges stacking within each other. This is explained vi- sually in figure 11 for a fraction of a complete graph. Each subsequent series of edges nests with the previous layer, increasing the overall stack height only by 2. As explained in...

    work page

  8. [8]

    M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information , 10th ed. (Cambridge Univer- sity Press, Cambridge ; New York, 2010)

    work page 2010

Show all 65 references
  1. [9]

    Coecke, T

    B. Coecke, T. Fritz, and R. W. Spekkens, A mathematical theory of resources, Information and Computation 250, 59 (2016)

    2016

  2. [10]

    Schmid, D

    D. Schmid, D. Rosset, and F. Buscemi, The type- independent resource theory of local operations and shared randomness, Quantum 4, 262 (2020)

    2020

  3. [11]

    Tilma, S

    T. Tilma, S. Hamaji, W. Munro, and K. Nemoto, En- tanglement is not a critical resource for quantum metrol- ogy, Physical Review A—Atomic, Molecular, and Optical Physics 81, 022108 (2010)

    2010

  4. [12]

    Catani, Non-classicality as a computational resource , Ph.D

    L. Catani, Non-classicality as a computational resource , Ph.D. thesis, UCL (University College London) (2018)

    2018

  5. [13]

    C. F. Kam, W. M. Zhang, and D. H. Feng, Coherent States: New Insights into Quantum Mechanics with Ap- plications (Springer, 2023)

    2023

  6. [14]

    Horodecki, P

    R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, Quantum entanglement, Reviews of mod- ern physics 81, 865 (2009)

    2009

  7. [15]

    Bengtsson and K

    I. Bengtsson and K. ˙Zyczkowski, Geometry of quantum states: an introduction to quantum entanglement (Cam- bridge university press, 2017)

    2017

  8. [16]

    Schmid, T

    D. Schmid, T. C. Fraser, R. Kunjwal, A. B. Sainz, E. Wolfe, and R. W. Spekkens, Understanding the in- terplay of entanglement and nonlocality: motivating and developing a new branch of entanglement theory, Quan- tum 7, 1194 (2023)

    2023

  9. [17]

    Scarani, Bell nonlocality (Oxford University Press, 2019)

    V. Scarani, Bell nonlocality (Oxford University Press, 2019)

    2019

  10. [18]

    Wolfe, D

    E. Wolfe, D. Schmid, A. B. Sainz, R. Kunjwal, and R. W. Spekkens, Quantifying bell: The resource theory of nonclassicality of common-cause boxes, Quantum 4, 280 (2020)

    2020

  11. [19]

    Rosset, D

    D. Rosset, D. Schmid, and F. Buscemi, Type- independent characterization of spacelike separated re- sources, Physical Review Letters 125, 210402 (2020)

    2020

  12. [20]

    Montanaro, Quantum algorithms: an overview, npj Quantum Information 2, 1 (2016), number: 1 Publisher: Nature Publishing Group

    A. Montanaro, Quantum algorithms: an overview, npj Quantum Information 2, 1 (2016), number: 1 Publisher: Nature Publishing Group

    2016

  13. [21]

    T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms, third edition ed. (MIT Press, Cambridge, Mass., 2009) oCLC: 311310321

    2009

  14. [22]

    Sipser, Introduction to the Theory of Computation , Vol

    M. Sipser, Introduction to the Theory of Computation , Vol. 27 (1996)

    1996

  15. [23]

    Bernstein and U

    E. Bernstein and U. Vazirani, Quantum Complexity The- ory, SIAM Journal on Computing 26, 1411 (1997), pub- lisher: Society for Industrial and Applied Mathematics

    1997

  16. [24]

    Ediger, K

    D. Ediger, K. Jiang, J. Riedy, D. A. Bader, C. Corley, R. Farber, and W. N. Reynolds, Massive Social Network Analysis: Mining Twitter for Social Good, in 2010 39th International Conference on Parallel Processing (2010) pp. 583–593, iSSN: 2332-5690

    2010

  17. [25]

    A. L. Traud, P. J. Mucha, and M. A. Porter, Social struc- ture of Facebook networks, Physica A: Statistical Me- chanics and its Applications 391, 4165 (2012)

    2012

  18. [26]

    C. J. Stam and J. C. Reijneveld, Graph theoretical anal- ysis of complex networks in the brain, Nonlinear Biomed- ical Physics 1, 3 (2007)

    2007

  19. [27]

    G. A. Pavlopoulos, M. Secrier, C. N. Moschopoulos, T. G. Soldatos, S. Kossida, J. Aerts, R. Schneider, and P. G. 12 0 200 400 600 800 101 102 103 Number of nodes Average depth of the circuit Depth of the circuit against number of nodes Figure 10. As the number of nodes increas...

    2011

  20. [28]

    F. V. Farahani, W. Karwowski, and N. R. Lighthall, Application of Graph Theory for Identifying Con- nectivity Patterns in Human Brain Networks: A Systematic Review, Frontiers in Neuroscience 13, 10.3389/fnins.2019.00585 (2019), publisher: Frontiers

    2019

  21. [29]

    P. R. Monge and N. S. Contractor, Theories of commu- nication networks (Oxford University Press, USA, 2003)

    2003

  22. [30]

    Enrico Fermi

    M. Hein, W. D¨ ur, J. Eisert, R. Raussendorf, M. Van den Nest, and H.-J. Briegel, Entanglement in graph states and its applications, Proceedings of the International School of Physics “Enrico Fermi” 162, 115 (2006)

    2006

  23. [31]

    Coecke and A

    B. Coecke and A. Kissinger, The Compositional Structure of Multipartite Quantum Entanglement, in Automata, Languages and Programming , edited by S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, and P. G. Spirakis (Springer, Berlin, Heidelberg,

  24. [32]

    de Beaudrap and M

    N. de Beaudrap and M. Roetteler, Quantum Linear Net- work Coding as One-way Quantum Computation, in 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014) (Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2014) pp. 217–233

    2014

  25. [33]

    K. P. Gnatenko and N. A. Susulovska, Geometric mea- sure of entanglement of multi-qubit graph states and its detection on a quantum computer, Europhysics Letters 136, 40003 (2022), publisher: EDP Sciences, IOP Pub- lishing and Societ` a Italiana di Fisica

    2022

  26. [34]

    Vesperini and R

    A. Vesperini and R. Franzosi, Entanglement, Quantum Correlators, and Connectivity in Graph States, Advanced Quantum Technologies 7, 2300264 (2024)

    2024

  27. [35]

    J. L. Gross and J. Yellen, eds., Handbook of graph theory, Discrete mathematics and its applications (CRC Press, Boca Raton, Fla., 2004)

    2004

  28. [36]

    M. O. Ball, C. J. Colbourn, and J. S. Provan, Network re- liability, in Handbooks in Operations Research and Man- agement Science, Network Models, Vol. 7 (Elsevier, 1995) pp. 673–762

    1995

  29. [37]

    S. E. Schaeffer, Graph clustering, Computer Science Re- view 1, 27 (2007)

    2007

  30. [38]

    Erciyes, Distributed Graph Algorithms for Computer Networks (Springer Science & Business Media, 2013)

    K. Erciyes, Distributed Graph Algorithms for Computer Networks (Springer Science & Business Media, 2013)

    2013

  31. [39]

    Shiloach and U

    Y. Shiloach and U. Vishkin, An O(logn) parallel connec- tivity algorithm, Journal of Algorithms 3, 57 (1982)

    1982

  32. [40]

    D¨ urr, M

    C. D¨ urr, M. Heiligman, P. Høyer, and M. Mhalla, Quan- tum Query Complexity of Some Graph Problems, SIAM Journal on Computing 35, 1310 (2006), publisher: Soci- ety for Industrial and Applied Mathematics

    2006

  33. [41]

    L. K. Grover, A fast quantum mechanical algorithm for database search, in Proceedings of the twenty-eighth an- nual ACM symposium on Theory of Computing , STOC ’96 (Association for Computing Machinery, New York, NY, USA, 1996) pp. 212–219

    1996

  34. [42]

    Coecke and R

    B. Coecke and R. Duncan, Interacting Quantum Ob- servables, in Automata, Languages and Programming , edited by L. Aceto, I. Damg ˚ ard, L. A. Goldberg, M. M. Halld´ orsson, A. Ing´ olfsd´ ottir, and I. Walukiewicz (Springer, Berlin, Heidelberg, 2008) pp. 298–310

    2008

  35. [43]

    Coecke and A

    B. Coecke and A. Kissinger, Picturing Quantum Pro- cesses: A First Course in Quantum Theory and Di- agrammatic Reasoning (Cambridge University Press, Cambridge, 2017)

    2017

  36. [44]

    van de Wetering, ZX-calculus for the working quantum computer scientist (2020), arXiv:2012.13966 [quant-ph]

    J. van de Wetering, ZX-calculus for the working quantum computer scientist (2020), arXiv:2012.13966 [quant-ph]

    2020 arXiv

  37. [45]

    Coecke and R

    B. Coecke and R. Duncan, Interacting quantum observ- ables: categorical algebra and diagrammatics, New Jour- nal of Physics 13, 043016 (2011), publisher: IOP Pub- lishing

    2011

  38. [46]

    Vilmart, A near-minimal axiomatisation of zx-calculus for pure qubit quantum mechanics, in 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (2019) pp

    R. Vilmart, A near-minimal axiomatisation of zx-calculus for pure qubit quantum mechanics, in 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (2019) pp. 1–10

    2019

  39. [47]

    Wang and R

    Q. Wang and R. Yeung, Representing and Imple- menting Matrices Using Algebraic ZX-calculus (2023), arXiv:2110.06898. 13

    2023 arXiv

  40. [48]

    Terashima and M

    H. Terashima and M. Ueda, Nonunitary quantum circuit, International Journal of Quantum Information 03, 633 (2005), publisher: World Scientific Publishing Co

    2005

  41. [49]

    Brassard, P

    G. Brassard, P. Høyer, M. Mosca, and A. Tapp, Quantum amplitude amplification and estimation, Contemporary Mathematics 305, 53 (2002), publisher: Providence, RI; American Mathematical Society; 1999

    2002

  42. [52]

    Renner, Simplifying information-theoretic arguments by post-selection, in Quantum Cryptography and Com- puting (IOS Press, 2010) pp

    R. Renner, Simplifying information-theoretic arguments by post-selection, in Quantum Cryptography and Com- puting (IOS Press, 2010) pp. 66–75

    2010

  43. [53]

    Wright, Automatic post-selection by ancillae ther- malization, Physical Review Research 3, 10.1103/Phys- RevResearch.3.033151 (2021)

    L. Wright, Automatic post-selection by ancillae ther- malization, Physical Review Research 3, 10.1103/Phys- RevResearch.3.033151 (2021)

    2021 doi

  44. [54]

    Poulin, Stabilizer Formalism for Operator Quan- tum Error Correction, Physical Review Letters 95, 10.1103/PhysRevLett.95.230504 (2005)

    D. Poulin, Stabilizer Formalism for Operator Quan- tum Error Correction, Physical Review Letters 95, 10.1103/PhysRevLett.95.230504 (2005)

    2005 doi

  45. [55]

    D. S. Abrams and S. Lloyd, Nonlinear Quan- tum Mechanics Implies Polynomial-Time Solution for $\mathit{NP}$-Complete and # $\mathit{P}$ Prob- lems, Physical Review Letters 81, 3992 (1998), publisher: American Physical Society

    1998

  46. [56]

    C. Song, K. Xu, H. Li, Y.-R. Zhang, X. Zhang, W. Liu, Q. Guo, Z. Wang, W. Ren, J. Hao, H. Feng, H. Fan, D. Zheng, D.-W. Wang, H. Wang, and S.-Y. Zhu, Gen- eration of multicomponent atomic Schr¨ odinger cat states of up to 20 qubits, Science 365, 574 (2019), publisher: American...

    2019

  47. [57]

    G. J. Mooney, G. A. L. White, C. D. Hill, and L. C. L. Hollenberg, Generation and verification of 27- qubit Greenberger-Horne-Zeilinger states in a supercon- ducting quantum computer, Journal of Physics Commu- nications 5, 095004 (2021), publisher: IOP Publishing

    2021

  48. [58]

    G. J. Mooney, G. A. L. White, C. D. Hill, and L. C. L. Hollenberg, Whole-Device Entanglement in a 65-Qubit Superconducting Quantum Computer, Advanced Quan- tum Technologies 4, 2100061 (2021)

    2021

  49. [59]

    Y. Zhao, R. Zhang, W. Chen, X.-B. Wang, and J. Hu, Creation of Greenberger-Horne-Zeilinger states with thousands of atoms by entanglement amplification, npj Quantum Information 7, 1 (2021), publisher: Nature Publishing Group

    2021

  50. [60]

    H. J. Briegel, D. E. Browne, W. D¨ ur, R. Raussendorf, and M. Van den Nest, Measurement-based quantum compu- tation, Nature Physics 5, 19 (2009), publisher: Nature Publishing Group

    2009

  51. [61]

    Kissinger and J

    A. Kissinger and J. v. d. Wetering, Universal MBQC with generalised parity-phase interactions and Pauli measure- ments, Quantum 3, 134 (2019), publisher: Verein zur F¨ orderung des Open Access Publizierens in den Quan- tenwissenschaften

    2019

  52. [62]

    Duncan and S

    R. Duncan and S. Perdrix, Rewriting Measurement- Based Quantum Computations with Generalised Flow, in Automata, Languages and Programming , edited by S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, and P. G. Spirakis (Springer, Berlin, Heidelberg,

  53. [63]

    J. L. Beckey, Multipartite entanglement measures via Bell-basis measurements, Physical Review A 107, 10.1103/PhysRevA.107.062425 (2023)

    2023 doi

  54. [64]

    Bezanson, A

    J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, Julia: A fresh approach to numerical computing, SIAM review 59, 65 (2017)

    2017

  55. [65]

    Luo, J.-G

    X.-Z. Luo, J.-G. Liu, P. Zhang, and L. Wang, Yao.jl: Extensible, Efficient Framework for Quantum Algorithm Design, Quantum 4, 341 (2020), arXiv: 1912.10877

    2020 arXiv

  56. [66]

    Erd˝ os and A

    P. Erd˝ os and A. R´ enyi, On random graphs. I., Publica- tiones Mathematicae Debrecen 6, 290 (1959)

    1959

  57. [67]

    Mertens, The Easiest Hard Problem: Number Par- titioning, in Computational Complexity and Statistical Physics (Oxford University Press, 2005)

    S. Mertens, The Easiest Hard Problem: Number Par- titioning, in Computational Complexity and Statistical Physics (Oxford University Press, 2005)

    2005

Pith tools

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