Pith. sign in

REVIEW 2 major objections 5 minor 1 cited by

This paper proves a tight lower bound for graphic parity networks—CNOT-only quantum circuits that realize every edge of a graph as a parity term and restore their inputs—and gives a randomized synthesis whose expected size nearly matches it

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

The minimum size of a graphic parity network for a connected graph is at least m+n-1, rising to m+Omega(n^1.5) for graphs with no short cycles, and a randomized construction achieves m+O(n^1.5 sqrt(log n)).

T0 review reviewed 2026-08-04 challenge →

load-bearing objection Strong lower-bound and graph-theory results in parity network synthesis, but the randomized algorithm's key lemma has an unproved monotonicity step that needs work. the 2 major comments →

arxiv 2509.10070 v1 pith:EDYZQZCV submitted 2025-09-12 quant-ph cs.DMcs.DSmath.CO

Toward Minimum Graphic Parity Networks

Yixin Cao , Yiren Lu , Junhong Nie , Xiaoming Sun , Guojing Tian This is my paper
classification quant-ph cs.DMcs.DSmath.CO
keywords graphic parity networkCNOT circuit synthesisquantum circuit optimizationperfect cancellation graphperfect cancellation orderinglower boundQAOAtreewidth
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

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 asks how few CNOT gates are needed to build a graphic parity network: a CNOT-only quantum circuit that, for every edge of a graph, produces the parity of the two endpoint qubits at some point, while returning all qubits to their original values. For a connected graph with n vertices and m edges, the answer is at least m+n-1 gates; the proof counts operations that merge disconnected parts of the term hypergraph. When the graph has no cycles shorter than five, the lower bound jumps to m+Ω(m), which can be as large as m+Ω(n^1.5) for suitable sparse graphs. The paper also gives a simple randomized algorithm that synthesizes a network of expected size m+O(n^1.5√log n), nearly matching the lower bound, and it identifies a new graph class, perfect cancellation graphs, conjectured to be exactly those graphs admitting optimal networks.

Core claim

Any graphic parity network for a connected graph with n vertices and m edges requires at least m+n-1 CNOT gates. The proof shows that at least n-1 operations must produce non-binary terms, because only such operations can reduce the number of connected components in the evolving set of generated parity terms; the remaining m operations can generate the m edge terms. For graphs of girth at least five, the lower bound improves to m+Ω(m), and since there exist graphs with Ω(n^1.5) edges and girth at least five, this becomes m+Ω(n^1.5) for such graphs. A complementary randomized algorithm, which processes vertices in a random order and exploits triangles and squares for cancellations, synthesize

What carries the argument

The central object is the perfect cancellation ordering: an ordering σ of the vertices such that for every vertex v, the set of neighbors of v appearing after v in σ, restricted to any component of G−v, is σ-linked, meaning consecutive vertices in that restricted order are adjacent. This ordering captures when edge terms can be generated by cancellation—each new edge cancels a shared element from a previous term—so that a linear-time algorithm can synthesize an optimal network. The lower-bound arguments instead use a counting mechanism on terms: tracking how the number of connected components of the hypergraph of generated terms decreases, and counting operations whose output is non-binary.

Load-bearing premise

The expected-size bound for the randomized algorithm rests on an unproved inequality that reduces the count of extra gates to the case where the first vertex is placed in the first position; if that comparison fails, the m+O(n^1.5√log n) guarantee is not yet established.

What would settle it

Brute-force enumerate all vertex permutations for a small asymmetric graph, such as a triangle with a long pendant path, and compare the algorithm's total number of line-12 executions across all permutations with n times the count when a fixed vertex is forced into position 1. Any graph violating the inequality labeled (1) in Lemma 2.7 would refute Theorem 1.3's proof; if all small graphs satisfy it, the missing exchange argument likely exists.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Every graphic parity network for a connected graph needs at least m+n−1 gates, so any CNOT-only circuit that realizes all graph edges and restores its inputs is forced to pay this baseline cost.
  • For graphs of girth at least five, the minimum size is m+Ω(m); combined with the existence of such graphs with Ω(n^1.5) edges, this gives a strong lower bound of m+Ω(n^1.5) for those graphs.
  • The randomized algorithm almost matches the lower bound in expectation, producing networks of size m+O(n^1.5√log n) in polynomial time, and m+O(n log n) for graphs with almost all vertices having linear degree.
  • All perfect cancellation graphs admit optimal graphic parity networks, synthesizable in linear time, and the paper conjectures that these are exactly the graphs with optimal networks.
  • Recognizing perfect cancellation graphs is NP-complete, but becomes fixed-parameter tractable when parameterized by treewidth.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Inference — The lower-bound mechanism, which counts non-binary operations via component merges, is not specific to two-element terms; it should transfer to parity networks for general set families, where the same component-count argument bounds the number of non-singleton outputs.
  • Inference — Since each newly generated binary term is exactly where an Rz gate would be inserted in QAOA or adiabatic circuits, the size bounds can be read as gate-count bounds for those algorithms' phase-separation circuits, making the m+Ω(n^1.5) case a concrete obstacle for high-girth sparse instances.
  • Inference — A testable extension is to run the randomized algorithm on random regular graphs of girth five and on chordal graphs, comparing empirical overhead against the dense-case bound m+O(n log n) and the general m+O(n^1.5√log n) bound, and to check whether the perfect cancellation orderings can be found by local search on small graphs.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies graphic parity networks: CNOT-only circuits over n wires that realize each edge of an input graph as a binary term at some intermediate time and return all wires to singleton terms. The main results are: (1) a lower bound of m+n-c gates for any graphic parity network of an n-vertex, m-edge graph with c components (Theorem 1.1); (2) an improved m+Omega(m) lower bound for graphs of girth at least five, combined with an extremal construction to obtain m+Omega(n^{3/2}) for such graphs (Theorem 1.2); (3) a randomized synthesis algorithm with expected size m+O(n^{3/2} sqrt(log n)) (Theorem 1.3); and (4) a study of graphs admitting perfect graphic parity networks ("perpane"), including a candidate characterization by "perfect cancellation orderings," a linear-time synthesis algorithm for that class, NP-completeness of recognition, and a claimed fixed-parameter tractable recognition algorithm parameterized by treewidth. The paper also states a conjecture that perpane graphs coincide with perfect cancellation graphs.

Significance. If the results stand, the paper gives the first theoretical performance guarantees for graphic parity network synthesis, a problem motivated by QAOA/QAA circuits. The lower bounds in Lemma 2.2 and Lemma 2.3 are clean and appear correct, and the introduction of perfect cancellation graphs is a useful organizing concept. The randomized algorithm is simple and, if the main inequality can be justified, nearly matches the lower-bound construction. The NP-completeness reduction from Betweenness is plausible and the connection between perfect cancellation orderings and elimination orderings is natural. However, two load-bearing claims currently rest on unproved material: the key inequality in Lemma 2.7, on which Theorem 1.3 depends, and the fixed-parameter tractability of recognition, which is only sketched in Appendix F. These gaps prevent the stated results from being considered established.

major comments (2)
  1. [Section 2.3, Lemma 2.7, equation (1)] Equation (1) is asserted without proof, and it is load-bearing for Theorem 1.3. The preceding display reindexes the positions at which the first vertex u can appear, but no argument shows that the expected number of line-12 pairs with u at position n-j+1 is at most the expected number with u at position 1. The line-12 count is not invariant under moving u to the front: the set of later vertices changes, and condition (iv) depends on the interval (u,v). A coupling or monotonicity argument is needed, and none is supplied. If (1) fails, the bound (5) and hence the m+O(n^{1.5} sqrt(log n)) upper bound are not established.
  2. [Section 3.2 / Appendix F] Theorem 1.6 claims that recognition of perfect cancellation graphs is FPT parameterized by treewidth, but Appendix F is explicitly a sketch. It describes transitions for introduce, forget, and join nodes, but it does not state a precise DP invariant, does not prove that the canonical representation set c_t has size bounded by a function of the treewidth k, and gives no runtime bound of the form f(k)n^{O(1)}. Without these components, the FPT claim is unproved. This is a central contribution and needs a complete proof.
minor comments (5)
  1. [Proof of Theorem 1.5] The text refers to "Theorem 3.1" when applying the false-twin lemma; the stated result is Lemma 3.1.
  2. [Proof of Theorem 1.5, necessity part] In the verification of the constructed ordering, the sentence about non-adjacent pairs says "1 <= j < i <= q" but the elements x_j and x_i range over S, so the index bound should be 1 <= j < i <= p.
  3. [Abstract and Section 1] The abstract says the m+Omega(n^{1.5}) lower bound holds "when the shortest cycle in the graph has length at least five." Strictly, Lemma 2.3 gives m+Omega(m) for every girth-five graph; the n^{3/2} form follows only after applying Lemma 2.4 to graphs that actually have Omega(n^{1.5}) edges. This should be stated more carefully.
  4. [Appendix E] The sentence "Theorem 1.3 is thus a direct consequence of Theorem 2.6 and Theorem 2.7" should refer to Lemma 2.6 and Lemma 2.7.
  5. [Appendix C] The proof refers to "theorem C.2" after naming it Lemma C.2; the label should be consistent.

Circularity Check

0 steps flagged

No circularity: lower bounds, algorithm analysis, and recognition results are derived from definitions and external benchmarks.

full rationale

The paper's central derivation chain is self-contained rather than circular. The main lower bound (Theorem 1.1) follows from Lemma 2.2, which is proved directly from the circuit model: a connected graph requires at least n-1 plus-operations because the hypergraph of generated terms must go from n components to 1, and then non-binary-term operations are counted in the inverse network. This is a genuine combinatorial proof with no fitted quantity or assumption equivalent to the conclusion. The girth-five lower bound (Lemma 2.3) is an independent counting argument over the operations f(e), c(e), and R; it does not import the desired bound as an assumption. The construction for Theorem 1.2 uses the external fact that finite projective planes exist and have high girth, plus Bertrand's Postulate, neither of which presupposes anything about parity networks. The randomized algorithm's expected size bound is an analysis of the algorithm's own behavior: it counts line-12 executions and bounds them using degree thresholds and a probabilistic calculation over random permutations. The questionable inequality (1) in Lemma 2.7 is an asserted analytic step that is not proved; if false, Theorem 1.3 would be weakened, but this is a correctness risk, not circularity, because the inequality is not used as a definition of the output nor is the conclusion baked into the algorithm's behavior. The perfect cancellation graph class is defined independently (via sigma-linked neighborhoods) and then shown to imply perpane through Algorithm 1 and its invariant proof; the converse is explicitly left as Conjecture 1 and is never used as an assumption. The NP-completeness proof reduces from the external Betweenness problem of Opatrny, and the FPT algorithm is a standard tree-decomposition dynamic program. The few self-citations in the introduction (e.g., [15], [34]) appear only as background references on CNOT optimization and are not load-bearing for any theorem. No step exhibits a prediction that reduces by construction to its inputs, no fitted parameter is renamed as a prediction, and no load-bearing uniqueness claim is imported from the authors' prior work.

Axiom & Free-Parameter Ledger

0 free parameters · 6 axioms · 1 invented entities

The central results rest on standard mathematical tools (projective planes, Bertrand's postulate) and on the modeling decision that a graphic parity network must exactly restore the input, not just permute it. The only newly introduced concept is the perfect cancellation graph, which is defined and then used to prove positive results; it is not a hidden assumption.

axioms (6)
  • standard math CNOT gates are linear operations over F2, so a CNOT-only circuit corresponds to row additions on an n×n binary matrix.
    Used in Appendix A to connect circuit synthesis to Gaussian elimination; standard linear algebra.
  • standard math For every prime power k there exists a finite projective plane of order k.
    Cited [19] and used in Lemma 2.4 to construct girth-at-least-five graphs with Omega(n^1.5) edges.
  • standard math Bertrand's postulate: for any integer n>1 there is a prime p with n<p<2n.
    Cited [8] and used in the proof of Lemma C.2 to ensure a sufficiently large prime below a given bound.
  • domain assumption The input graph is finite and simple.
    Stated at the start of Section 2; all proofs assume simple undirected graphs.
  • domain assumption A graphic parity network must restore the original input exactly, not a permutation of it.
    Stated in Appendix A; this exact-restoration requirement is used in Lemma 2.2 where final states must be singleton terms.
  • standard math The random permutation used by Algorithm 2 is uniform over all permutations of the vertices.
    Used in the expectation analysis of Lemma 2.7; standard probabilistic assumption.
invented entities (1)
  • perfect cancellation graph and perfect cancellation ordering no independent evidence
    purpose: Defines the class of graphs for which the paper can synthesize a minimum-size (m+n-1) graphic parity network in linear time; conjectured to coincide with perpane graphs.
    New mathematical definition introduced in Section 2.2. It has no falsifiable handle outside the paper; its value is internal to the theory developed here.

reviewed 2026-08-04 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Toward Minimum Graphic Parity Networks." pith.science (2026). https://pith.science/paper/EDYZQZCV

@misc{pith2026250910070,
  author       = {Pith},
  title        = {Pith review of: Toward Minimum Graphic Parity Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EDYZQZCV}},
  note         = {Machine review of arXiv:2509.10070}
}
Share X Bluesky LinkedIn Reddit HN
abstract

Quantum circuits composed of CNOT and $R_z$ are fundamental building blocks of many quantum algorithms, so optimizing the synthesis of such quantum circuits is crucial. We address this problem from a theoretical perspective by studying the graphic parity network synthesis problem. A graphic parity network for a graph $G$ is a quantum circuit composed solely of CNOT gates where each edge of $G$ is represented in the circuit, and the final state of the wires matches the original input. We aim to synthesize graphic parity networks with the minimum number of gates, specifically for quantum algorithms addressing combinatorial optimization problems with Ising formulations. We demonstrate that a graphic parity network for a connected graph with $n$ vertices and $m$ edges requires at least $m+n-1$ gates. This lower bound can be improved to $m+\Omega(m) = m+\Omega(n^{1.5})$ when the shortest cycle in the graph has a length of at least five. We complement this result with a simple randomized algorithm that synthesizes a graphic parity network with expected $m + O(n^{1.5}\sqrt{\log n})$ gates. Additionally, we begin exploring connected graphs that allow for graphic parity networks with exactly $m+n-1$ gates. We conjecture that all such graphs belong to a newly defined graph class. Furthermore, we present a linear-time algorithm for synthesizing minimum graphic parity networks for graphs within this class. However, this graph class is not closed under taking induced subgraphs, and we show that recognizing it is $\textsf{NP}$-complete, which is complemented with a fixed-parameter tractable algorithm parameterized by the treewidth.

Figures

Figures reproduced from arXiv: 2509.10070 by Guojing Tian, Junhong Nie, Xiaoming Sun, Yiren Lu, Yixin Cao.

Figure 1
Figure 1. Figure 1: Two graphic parity networks for the graph with edges [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: (a) A chordal graph, and (b) K2,p, which can be made chordal by adding the edge (1, 2). Our contributions. The number of gates in a graphic parity network is called its size. Let G be the input graph, and let n and m denote the numbers of vertices and edges, respectively, 1To make our work accessible to a general audience, we will minimize the use of quantum computing jargon in the main text. Consequently,… view at source ↗
Figure 3
Figure 3. Figure 3: Illustration for Theorem 3.1, where I = {z1, . . . , z4} and v1v2v3 is an induced path. Note that v1, v2, v3 might have other neighbors. We add an edge between each pair of vertices in C unless they have the same superscript (note that the complement of the subgraph induced by C is an induced matching), and we add all the 2pq edges between S and C. Third, we add a set U of p vertices, and make them univers… view at source ↗
Figure 4
Figure 4. Figure 4: The construction for the proof of Theorem 1.5. [PITH_FULL_IMAGE:figures/full_fig_p012_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Perfect graphic parity networks that do not satisfy the conditions. (a) A line of length [PITH_FULL_IMAGE:figures/full_fig_p014_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The corresponding circuit of the parity network in fig. 1b. It is generated by inserting a [PITH_FULL_IMAGE:figures/full_fig_p020_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: (a) The parity network fig. 1b and (b) its inverse. [PITH_FULL_IMAGE:figures/full_fig_p020_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: (a) The Fano plane, a finite projective plane of order 2, and (b) the bipartite graph [PITH_FULL_IMAGE:figures/full_fig_p021_8.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

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

  1. CNOT-Distance is NP-complete under all-to-all connectivity

    quant-ph 2026-08 accept novelty 7.0

    CNOT-Distance, deciding whether a given invertible binary matrix can be implemented with at most K CNOT gates under all-to-all connectivity, is NP-complete.

Reference graph

Works this paper leans on

46 extracted references · 7 canonical work pages · cited by 1 Pith paper

  1. [1]

    On the controlled-NOT com- plexity of controlled-NOT–phase circuits.Quantum Science and Technology, 4(1):015002, September 2018.doi:10.1088/2058-9565/aad8ca

    Matthew Amy, Parsiad Azimzadeh, and Michele Mosca. On the controlled-NOT com- plexity of controlled-NOT–phase circuits.Quantum Science and Technology, 4(1):015002, September 2018.doi:10.1088/2058-9565/aad8ca

    doi:10.1088/2058-9565/aad8ca 2018

  2. [2]

    Concentration Bounds for Quantum States and Limitations on the QAOA from Polynomial Approximations

    Anurag Anshu and Tony Metger. Concentration Bounds for Quantum States and Limitations on the QAOA from Polynomial Approximations. InDROPS- IDN/v2/Document/10.4230/LIPIcs.ITCS.2023.5. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023.doi:10.4230/LIPIcs.ITCS.2023.5

    work page doi:10.4230/lipics.itcs.2023.5 2023

  3. [3]

    The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model

    Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou. The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model. InDROPS- IDN/v2/Document/10.4230/LIPIcs.TQC.2022.7. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.doi:10.4230/LIPIcs.TQC.2022.7

    doi:10.4230/lipics.tqc.2022.7 2022

  4. [4]

    Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models

    Joao Basso, David Gamarnik, Song Mei, and Leo Zhou. Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models. In2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 335–343, October 2022.doi:10.1109/FOCS54457.2022.00039

    arXiv 2022

  5. [5]

    Cross, Jay M

    Sergey Bravyi, Andrew W. Cross, Jay M. Gambetta, Dmitri Maslov, Patrick Rall, and Theodore J. Yoder. High-threshold and low-overhead fault-tolerant quantum memory. Nature, 627(8005):778–782, March 2024.doi:10.1038/s41586-024-07107-7

    doi:10.1038/s41586-024-07107-7 2024

  6. [6]

    Fixed-parameter tractability of graph modification problems for heredi- tary properties.Information Processing Letters, 58(4):171–176, 1996

    Leizhen Cai. Fixed-parameter tractability of graph modification problems for heredi- tary properties.Information Processing Letters, 58(4):171–176, 1996. doi:10.1016/ 0020-0190(96)00050-6

    1996

  7. [7]

    Generation of genuine entanglement up to 51 superconducting qubits.Nature, 619(7971):738–742, July 2023.doi:10.1038/s41586-023-06195-1

    Sirui Cao, Bujiao Wu, Fusheng Chen, Ming Gong, Yulin Wu, Yangsen Ye, Chen Zha, Haoran Qian, Chong Ying, Shaojun Guo, Qingling Zhu, He-Liang Huang, Youwei Zhao, Shaowei Li, Shiyu Wang, Jiale Yu, Daojin Fan, Dachao Wu, Hong Su, Hui Deng, Hao Rong, Yuan Li, Kaili Zhang, Tung-Hsun Chung, Futian Liang, Jin Lin, Yu Xu, Lihua Sun, Cheng Guo, Na Li, Yong-Heng Huo...

    2023

  8. [8]

    Mémoire sur les nombres premiers.Journal de mathématiques pures et appliquées, Série 1:366–390, 1852

    Pafnuty Lvovich Chebyshev. Mémoire sur les nombres premiers.Journal de mathématiques pures et appliquées, Série 1:366–390, 1852. Proof of the postulate: 371–382

  9. [9]

    Faster and shorter synthesis of Hamil- tonian simulation circuits, April 2024.arXiv:2404.03280

    Timothée Goubault de Brugière and Simon Martiel. Faster and shorter synthesis of Hamil- tonian simulation circuits, April 2024.arXiv:2404.03280

    Pith/arXiv arXiv 2024

  10. [10]

    A Quantum Approximate Optimization Algorithm.arXiv:1411.4028 [quant-ph], November 2014.arXiv:1411.4028

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Optimization Algorithm.arXiv:1411.4028 [quant-ph], November 2014.arXiv:1411.4028

    Pith/arXiv arXiv 2014

  11. [11]

    Quantum Computation by Adiabatic Evolution, January 2000.arXiv:quant-ph/0001106

    Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum Computation by Adiabatic Evolution, January 2000.arXiv:quant-ph/0001106

    Pith/arXiv arXiv 2000

  12. [12]

    Vlad Gheorghiu, Jiaxin Huang, Sarah Meng Li, Michele Mosca, and Priyanka Mukhopad- hyay. Reducing the CNOT Count for Clifford+T Circuits on NISQ Architectures.IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 42(6):1873–1884, June 2023.doi:10.1109/TCAD.2022.3213210. 15

    arXiv 2023

  13. [13]

    Shallower cnot circuits on realistic quantum hardware.ACM Transactions on Quantum Computing, November 2024

    Timothée Goubault de Brugière and Simon Martiel. Shallower cnot circuits on realistic quantum hardware.ACM Transactions on Quantum Computing, November 2024. Just Accepted.doi:10.1145/3700884

    work page doi:10.1145/3700884 2024

  14. [14]

    Harrigan, Kevin J

    Matthew P. Harrigan, Kevin J. Sung, Matthew Neeley , Kevin J. Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C. Bardin, Rami Barends, Sergio Boixo, Michael Broughton, Bob B. Buckley, David A. Buell, Brian Burkett, Nicholas Bushnell, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney , Sean Demura, Andrew Dunsworth, Daniel Eppens,...

    2021

  15. [15]

    Optimal space-depth trade-off of cnot circuits in quantum logic synthesis

    Jiaqing Jiang, Xiaoming Sun, Shang-Hua Teng, Bujiao Wu, Kewen Wu, and Jialin Zhang. Optimal space-depth trade-off of cnot circuits in quantum logic synthesis. InProceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’20, pages 213–229, USA, 2020. Society for Industrial and Applied Mathematics

    2020

  16. [16]

    Algorithm 447: Efficient algorithms for graph manipula- tion.Communications of the ACM, June 1973.doi:10.1145/362248.362272

    Hopcroft John and Tarjan Robert. Algorithm 447: Efficient algorithms for graph manipula- tion.Communications of the ACM, June 1973.doi:10.1145/362248.362272

    arXiv 1973

  17. [17]

    Exponential Quantum Space Ad- vantage for Approximating Maximum Directed Cut in the Streaming Model

    John Kallaugher, Ojas Parekh, and Nadezhda Voronova. Exponential Quantum Space Ad- vantage for Approximating Maximum Directed Cut in the Streaming Model. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1805–1815, Vancouver BC Canada, June 2024. ACM.doi:10.1145/3618260.3649709

    arXiv 2024

  18. [18]

    Tractability of parameterized com- pletion problems on chordal, strongly chordal, and proper interval graphs.SIAM Journal on Computing, 28(5):1906–1922, 1999

    Haim Kaplan, Ron Shamir, and Robert Endre Tarjan. Tractability of parameterized com- pletion problems on chordal, strongly chordal, and proper interval graphs.SIAM Journal on Computing, 28(5):1906–1922, 1999. A preliminary version appeared in FOCS 1994. doi:10.1137/S0097539796303044

    work page doi:10.1137/s0097539796303044 1906

  19. [19]

    North-Holland Publishing Company, 1976

    Ferenc Kárteszi.Introduction to Finite Geometries. North-Holland Publishing Company, 1976

    1976

  20. [20]

    Error per single-qubit gate below 10−4 in a superconducting qubit.npj Quantum Information, 9(1):111, 2023.doi:10.1038/s41534-023-00781-x

    Zhiyuan Li, Pei Liu, Peng Zhao, Zhenyu Mi, Huikai Xu, Xuehui Liang, Tang Su, Weijie Sun, Guangming Xue, Jing-Ning Zhang, Weiyang Liu, Yirong Jin, and Haifeng Yu. Error per single-qubit gate below 10−4 in a superconducting qubit.npj Quantum Information, 9(1):111, 2023.doi:10.1038/s41534-023-00781-x

    work page doi:10.1038/s41534-023-00781-x 2023

  21. [21]

    Ising formulations of many NP problems.Frontiers in Physics, 2,

    Andrew Lucas. Ising formulations of many NP problems.Frontiers in Physics, 2,

  22. [22]

    Depth optimization of cz, cnot, and clifford circuits.IEEE Transactions on Quantum Engineering, 3:1–8, 2022.doi:10.1109/TQE.2022.3180900

    Dmitri Maslov and Ben Zindorf. Depth optimization of cz, cnot, and clifford circuits.IEEE Transactions on Quantum Engineering, 3:1–8, 2022.doi:10.1109/TQE.2022.3180900

    arXiv 2022

  23. [23]

    Quan- tum Circuits for General Multiqubit Gates.Physical Review Letters, 93(13):130502, sep 2004

    Mikko Möttönen, Juha J Vartiainen, Ville Bergholm, and Martti M Salomaa. Quan- tum Circuits for General Multiqubit Gates.Physical Review Letters, 93(13):130502, sep 2004. URL: https://link.aps.org/doi/10.1103/PhysRevLett.93.130502, doi: 10.1103/PhysRevLett.93.130502

    doi:10.1103/physrevlett.93.130502 2004

  24. [24]

    Ross, Yuan Su, Andrew M

    Yunseong Nam, Neil J. Ross, Yuan Su, Andrew M. Childs, and Dmitri Maslov. Automated op- timization of large quantum circuits with continuous parameters.npj Quantum Information, 4(1):1–12, May 2018.doi:10.1038/s41534-018-0072-4

    doi:10.1038/s41534-018-0072-4 2018

  25. [25]

    Beating the break-even point with a discrete-variable-encoded logical qubit.Nature, 616(7955):56–60, April 2023.doi:10.1038/s41586-023-05784-4

    Zhongchu Ni, Sai Li, Xiaowei Deng, Yanyan Cai, Libo Zhang, Weiting Wang, Zhen-Biao Yang, Haifeng Yu, Fei Yan, Song Liu, Chang-Ling Zou, Luyan Sun, Shi-Biao Zheng, Yuan Xu, and Dapeng Yu. Beating the break-even point with a discrete-variable-encoded logical qubit.Nature, 616(7955):56–60, April 2023.doi:10.1038/s41586-023-05784-4

    work page doi:10.1038/s41586-023-05784-4 2023

  26. [26]

    Total Ordering Problem.SIAM Journal on Computing, 8(1):111–114, 1979.doi:10.1137/0208008

    Jaroslav Opatrny. Total Ordering Problem.SIAM Journal on Computing, 8(1):111–114, 1979.doi:10.1137/0208008

    work page doi:10.1137/0208008 1979

  27. [27]

    Collins, Arinjoy De, Paul W

    Guido Pagano, Aniruddha Bapat, Patrick Becker, Katherine S. Collins, Arinjoy De, Paul W. Hess, Harvey B. Kaplan, Antonis Kyprianidis, Wen Lin Tan, Christopher Baldwin, Lucas T. Brady , Abhinav Deshpande, Fangli Liu, Stephen Jordan, Alexey V. Gorshkov, and Christopher Monroe. Quantum approximate optimization of the long-range Ising model with a trapped- io...

    doi:10.1073/pnas.2006373117 2020

  28. [28]

    Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru-Guzik, and Jeremy L. O’Brien. A variational eigenvalue solver on a photonic quantum processor.Nature Communications, 5, 2014. doi:10.1038/ncomms5213

    doi:10.1038/ncomms5213 2014

  29. [29]

    Triangulated graphs and the elimination process.Journal of Mathematical Analysis and Applications, 32(3):597–609, December 1970

    Donald J Rose. Triangulated graphs and the elimination process.Journal of Mathematical Analysis and Applications, 32(3):597–609, December 1970. doi:10.1016/0022-247X(70) 90282-9

    work page doi:10.1016/0022-247x(70 1970

  30. [30]

    Dreiling, John P

    Ruslan Shaydulin, Changhao Li, Shouvanik Chakrabarti, Matthew DeCross, Dylan Herman, Niraj Kumar, Jeffrey Larson, Danylo Lykov, Pierre Minssen, Yue Sun, Yuri Alexeev, Joan M. Dreiling, John P. Gaebler, Thomas M. Gatterman, Justin A. Gerber, Kevin Gilmore, Dan Gresh, Nathan Hewitt, Chandler V. Horst, Shaohan Hu, Jacob Johansen, Mitchell Matheny , Tanner Me...

    2024

  31. [31]

    Masuo Suzuki. General theory of fractal path integrals with applications to many-body theories and statistical physics.Journal of Mathematical Physics, 32(2):400–407, February 1991.doi:10.1063/1.529425

    doi:10.1063/1.529425 1991

  32. [32]

    Efficient Decomposition of Quantum Gates.Physical Review Letters, 92(17):177902, 2004

    Juha J Vartiainen, Mikko Möttönen, and Martti M Salomaa. Efficient Decomposition of Quantum Gates.Physical Review Letters, 92(17):177902, 2004. URL: https://link.aps. org/doi/10.1103/PhysRevLett.92.177902,doi:10.1103/PhysRevLett.92.177902. 17

    doi:10.1103/physrevlett.92.177902 2004

  33. [33]

    Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G. Rieffel. Quantum approximate optimization algorithm for MaxCut: A fermionic view.Physical Review A, 97(2):022304, February 2018.doi:10.1103/PhysRevA.97.022304

    doi:10.1103/physreva.97.022304 2018

  34. [34]

    Optimization of CNOT circuits on limited-connectivity architecture.Physical Review Re- search, 5(1):13065, 2023

    Bujiao Wu, Xiaoyu He, Shuai Yang, Lifu Shou, Guojing Tian, Jialin Zhang, and Xiaoming Sun. Optimization of CNOT circuits on limited-connectivity architecture.Physical Review Re- search, 5(1):13065, 2023. URL: https://link.aps.org/doi/10.1103/PhysRevResearch. 5.013065,doi:10.1103/PhysRevResearch.5.013065

    doi:10.1103/physrevresearch 2023

  35. [35]

    MaxCut quantum approximate optimization algorithm performance guarantees for p > 1.Physical Review A, 103(4):042612, April 2021

    Jonathan Wurtz and Peter Love. MaxCut quantum approximate optimization algorithm performance guarantees for p > 1.Physical Review A, 103(4):042612, April 2021. doi: 10.1103/PhysRevA.103.042612

    doi:10.1103/physreva.103.042612 2021

  36. [36]

    Fixed-angle conjectures for the quantum approximate optimization algorithm on regular MaxCut graphs.Physical Review A, 104(5):052419, November 2021.doi:10.1103/PhysRevA.104.052419

    Jonathan Wurtz and Danylo Lykov. Fixed-angle conjectures for the quantum approximate optimization algorithm on regular MaxCut graphs.Physical Review A, 104(5):052419, November 2021.doi:10.1103/PhysRevA.104.052419

    doi:10.1103/physreva.104.052419 2021

  37. [37]

    Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin. Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices.Physical Review X, 10(2):021067, June 2020. doi:10.1103/PhysRevX. 10.021067. 18 A More quantum background Letx,b∈F n 2 , thenx·b=x 1b1 ⊕x 2b2 ⊕ · · · ⊕xnbn. Definition([ 1...

    doi:10.1103/physrevx 2020

  38. [39]

    Select a HamiltonianH B such thatH B has a simple ground state

  39. [40]

    Initialize the quantum state to the ground state ofH B

  40. [41]

    Evolve the quantum state under a time-dependent Hamiltonian that gradually changes fromH B toH C

  41. [42]

    The final state of the quantum system is the ground state of HC, whose energy can be measured to obtain the solution to the maximum cut problem. In the quantum circuit model, for the evolving of quantum state under a gradually changing Hamiltonian, one common approach is Trotter–Suzuki decomposition [31], where exp(iHBθ) and exp(iHCθ) should be implemente...

  42. [43]

    segments do not intersect, i.e.,σ(p i)< σ(qi)< σ(pi+1),

  43. [44]

    the subset of elements inN+ σ (v) covered by this segment, i.e.,Ci ={v|v∈N + σ (v)∧σ(pi)⩽ σ(v)⩽σ(q i)}, isσ-linked,

  44. [45]

    there are no two consecutiveX t elements inσ| Ci, and

  45. [46]

    In our algorithm, when working from the leaves to the root, we will keep track of all canonical representations of σ|N+σ (v) for v∈X t

    all segments together cover allN + σ (v), i.e., Sk i=1 Ci \ {⊣,⊢}=N + σ (v). In our algorithm, when working from the leaves to the root, we will keep track of all canonical representations of σ|N+σ (v) for v∈X t. To be precise, for each node t∈V(T) , we will construct a setc t that consists of all pairs(τ,b)describing a valid orderσsuch that: (V1)τis the ...

  46. [2014]

    URL: http://journal.frontiersin.org/article/10.3389/fphy.2014.00005/ abstract,doi:10.3389/fphy.2014.00005. 16

    arXiv 2014

This paper was first reviewed by deepseek-v4-flash on August 4, 2026.