CS Paper Radar

Hidden Circuits and Exact Counting in Ordered Graphs

Chenghua Liu, Boning Meng

cs.CC cs.DS ·submitted 2026-09-16 05:13 UTC · v1
theory

Abstract

We prove that counting perfect matchings is $\#P$-complete under polynomial-time Turing reductions on each of three classes of simple, unweighted graphs: monotone graphs, unit interval graphs, and chordal permutation graphs. The monotone result settles the exact-counting complexity left open by Dyer, Jerrum, and Müller (JACM 2017), complementing their rapid-mixing theorem. Inspired by quantum circuits, our reductions implement a circuit simulation using globally coupled matching-transfer operators. The key construction is an exact projection, implemented by a polynomial-length sequence of normalized transfers, that restores tensor-product locality and makes encoded gates composable. Interpolation-based cancellation then reduces circuit evaluation to unweighted perfect-matching counts in all three classes. We also place Dyer and Müller's class QChains within the distance-hereditary graphs and give an $O(n^2)$-arithmetic-operation counting algorithm for the latter, improving the $O(n^4)$ bound obtainable from Curticapean and Marx (SODA 2016). Together with prior results, these advances complete the exact-counting classification of the graph classes in Dyer and Müller's diagram (SIDMA 2019).

Closest papers

Nearest neighbours by meaning across the whole index.

Polynomial-time local-unitary equivalence of graph states

cs.CC quant-phcond-mat.mtrl-sci ·2026-09-30 ·Yuxuan Zhang
similarity 0.69
Abstract

Local-unitary (LU) equivalence asks whether two quantum states differ only by independent changes of basis on their qubits. For graph states, whether this relation can be decided in polynomial time has remained open for over a decade. We give a deterministic algorithm that decides LU equivalence for graphs on $n$ labelled vertices in $\widetilde O(n^{6.38})$ bit operations and constructs exact single-qubit unitaries whenever the states are equivalent. Building on Claudet and Perdrix's quasipolynomial algorithm, we replace the enumeration of vertex subsets by a compact system of constraints generated from pairs and triples. The remaining graph transformation is found by solving linear equations over the binary field. These new steps cost $\widetilde O(n^5)$ bit operations; the inherited graph preprocessing sets the overall bound. We also count the local-Clifford (LC) classes of graph states within any LU class: their number is a power of two, computable within the same bound. For any given graph state, this decides whether single-qubit Clifford gates reach every graph state in its LU class, and supplies a counterexample when they do not. The method also decides LU equivalence of stabilizer codes encoding one logical qubit.

0.26

Entanglement Lower Bounds for Symmetric Quantum Circuits

cs.CC quant-phcs.LO ·2026-11-17 ·Davi Castro-Silva, Ryan Dancy, Sergii Strelchuk
theory similarity 0.69
Abstract

Symmetric circuits require every symmetry of the input to extend to an automorphism of the circuit. In the classical setting, their connection to descriptive complexity yields strong unconditional lower bounds. We extend this approach to the quantum model of symmetric computation defined by Castro-Silva, Gur, and Strelchuk (ITCS 2026), proving a tradeoff between circuit size and entanglement width (the smallest $b$ such that, on every computational-basis input, the state after each layer factors into states on at most $b$ qubits each). Our main result identifies a graph property decidable in classical polynomial time that no polynomial-size family of symmetric quantum circuits on $n$-vertex graphs with entanglement width $o(n/\log n)$ can compute. The bound holds for circuits with arbitrary one-qubit and two-qubit gates and unrestricted depth, and remains valid under the weaker notion of symmetry with respect to even permutations of vertices. Our proof is based on a new quantum pebble game based on the partial trace. The resulting indistinguishability theorem transfers classical pebble-game lower bounds to quantum circuits with restricted entanglement. By contrast, without entanglement restrictions, we show that every graph property in BQP can be computed by a uniform family of polynomial-size symmetric quantum circuits. Restricting to circuits with no entanglement at all, we show that polynomial-size symmetric quantum circuits with entanglement width 1 can compute every graph property definable in fixed-point logic with counting. Finally, we give an efficient symmetric implementation of QAOA for MAX 3XOR, providing a starting point for studying entanglement lower bounds in quantum optimization algorithms.

0.30

A Dichotomy for Exact Quantum Circuit Amplitudes

cs.CC ·2026-11-17 ·Chenghua Liu, Boning Meng
similarity 0.67
Abstract

We classify the complexity of exactly computing computational-basis amplitudes for circuits over any fixed finite library of unitary qubit gates, with each gate allowed to act on any ordered tuple of distinct wires. Exact evaluation is polynomial-time computable if all gates permute the computational basis up to phases, all preserve product states, or all become Clifford under a common diagonal one-qubit unitary change of basis on every wire. For every other library, the problem is $\#\mathrm P$-hard under polynomial-time Turing reductions. Our proof connects circuit amplitudes to the Boolean Holant classification of tensor contractions on arbitrary graphs. For an algebraic library containing a nonmonomial gate and an entangling gate, we show how to simulate the joint use of a symmetric maximally entangled state and its adjoint at polynomial cost, using only amplitude queries over the original library. This lets us evaluate unrestricted contractions of the resulting gate and boundary tensors. Unitarity and the computational-basis boundaries then restrict the tractable cases to the three forms above. Algebraic specialization extends the dichotomy to arbitrary fixed complex gate entries under a symbolic exact-output convention.

0.31

Predicting Resource Efficient Hamiltonian Decomposition for Continuous-Time Quantum Walk Simulations

cs.LG quant-ph ·2026-08-21 ·Mostafa Atallah, Rebekah Herrman, Zain H. Saleem
similarity 0.67
Abstract · 12 pages, 6 figures

Simulating a continuous-time quantum walk (CTQW) on a graph in the circuit model of quantum computing requires decomposing its Hamiltonian into terms that can be Trotterized into hardware-native gates. We consider two such decompositions: the standard Pauli decomposition and the recently introduced matching decomposition. Prior work suggests that the matching decomposition uses fewer CX gates on sparse graphs, while the Pauli decomposition uses fewer on denser graphs. Since CX gates dominate error and runtime on current hardware, we train machine learning models to predict, for a given graph, which of the two decompositions produces the smaller CX gate count. We train and evaluate on the complete population of all 11,117 connected eight-vertex graphs from Brendan McKay's database, so the class balance and overlap are measured directly rather than estimated. We use twelve features: ten topological properties of the graph and two that count the terms the Pauli and matching decompositions produce (n_Pauli and n_match), both computable without transpiling the simulation circuit. Standard topological properties alone provide little predictive power. Instead, the dominant signal comes from n_Pauli, a property of the Hamiltonian decomposition rather than an intrinsic property of the graph; degree variance is the only other feature that carries signal. Across a range of models the Matthews correlation coefficient (MCC) falls in a narrow band, from 0.569 untuned to 0.593 after tuning, so no single architecture stands out. We adopt a single-hidden-layer neural network at MCC 0.593. Applied frozen to a held-out, class-balanced test set of larger graphs (up to 256 vertices) from structured and Erdos-Renyi families, the model transfers, with MCC rising from 0.785 at N=8 to 1 at N>=64.

0.28

Finding full immersions is fixed-parameter tractable in labeled tour graphs

cs.DS math.CO ·2026-11-04 ·Hadas Barabash, Jim Geelen, Rose McCarty, Caleb McFarland, Paul Wollan
theory similarity 0.66
Abstract

We give an $O_H(n^5)$-time algorithm to test whether an $n$-vertex labeled tour graph has a full immersion isomorphic to a labeled tour graph $H$. A labeled tour graph is a connected $4$-regular graph whose edges are labeled by binary vectors of fixed length. To obtain a full immersion, a vertex may be removed only by pairing up its four incident edges and "splitting off" both pairs, summing the labels within each pair. Even for one-bit labels, no polynomial-time algorithm was previously known for arbitrary fixed $H$. Our main tool is of independent interest: we give an algorithmic min-max theorem that, in particular, characterizes the maximum number of odd-length circuits in a rooted circuit decomposition of an Eulerian graph. Our results have implications for vertex-minors, whose study is motivated by applications in quantum networking, connections with graph minor theory, and the goal of developing an irrelevant vertex technique for dense graphs. For vertex-minors, circle graphs play the same role as planar graphs do for graph minors. As a corollary of our main theorem, we obtain a fixed-parameter tractable algorithm for apex-vertex-minor testing in $k$-apex circle graphs. We also prove an irrelevant vertex theorem for such graphs of large rank-width. More broadly, our results are essential to forthcoming work of three of the authors proving a structure theorem for graphs with a forbidden vertex-minor. There, our min-max theorem plays the role of both the algorithmic $A$-paths and Two Paths Theorems.

0.31

A Quantum Scaling Algorithm for Maximum-Weight Perfect Matching in General Graphs

cs.DS quant-ph ·2026-09-30 ·Kourosh Mirsohi, Sandy Irani, Michael T. Goodrich
theory similarity 0.64
Abstract · 41 pages, 6 figures, 3 tables

Quantum speed-ups have been obtained for many fundamental graph problems, including most variants of matching. A notable exception, however, is the maximum-weight perfect matching (MWPM) problem in general graphs with integer edge weights, which is arguably the most challenging variant of matching. We present a quantum algorithm for MWPM in general graphs that runs in $\widetilde{O}(n m^{2/3}\log W)$ time, where $W$ is an upper bound on the magnitude of the edge weights. This is an improvement over the best known classical combinatorial bound of $\widetilde{O}(m\sqrt n \log W)$ in the dense regime, where $m\ge n^{3/2}$. To the best of our knowledge, this is the first quantum algorithm to obtain an asymptotic improvement over the best classical combinatorial algorithm for the MWPM problem in general graphs. The running time of our method accounts for QRAM initialization and access overheads up to polylogarithmic factors, as well as all classical updates to the data structures. At a high level, our algorithm is based on a classical framework due to Duan, Pettie, and Su, but our algorithm requires replacing certain classical tasks with quantum methods, alternative analysis of classical procedures, and the use of alternative data structures that can be implemented effectively in the QRAM model.

0.29

Vanilla Exact Synthesis of CNOT Circuits is NP-hard

cs.CC quant-ph ·2026-09-03 ·Chenjian Li, Ji Guan
theoryhighly cited similarity 0.64
Abstract

Exact CNOT synthesis seeks a minimum-size circuit implementing a given invertible binary linear transformation. We study its vanilla formulation: synthesis from the identity on fixed labeled qubits, without ancillas and with all-to-all connectivity. We prove that this problem is NP-hard and that its bounded decision version is NP-complete. Hardness persists even for unitriangular targets that are low-rank perturbations of the identity and under near-linear gate budgets. Our proof gives a polynomial-time reduction from the NP-complete Hamiltonian path problem on grid graphs. A unary hypercube embedding translates graph vertices into circuit parities and edge traversals into CNOT updates. The central challenge is that Hamiltonian paths require intermediate vertex visits, whereas exact synthesis constrains only the final transformation. We bridge this gap with a replicated recorder qubits construction that encodes the required parities in the final outputs, together with a tight gate budget that forces every sufficiently short implementation to trace a Hamiltonian path. Crucially, this path structure is enforced by the construction rather than imposed as a restriction on the circuit. The result directly implies NP-hardness for shortest word problem and Cayley-graph distance computation over $\mathrm{GL}(n,2)$ with elementary transvections as generators, as well as fixed-width sequential XOR program minimization. For CNOT-minimal exact phase polynomial synthesis, it yields NP-hardness with a zero phase polynomial; extending the reduction to grid-graph Hamiltonian cycle problem establishes hardness even when the final linear transformation is the identity. These complementary results show that the linear and phase components each independently suffice for NP-hardness of exact phase polynomial synthesis.

0.43

Tight Quantum Query Bounds for Minimum Cut and Multicut on Dense Graphs

cs.DS cs.CC ·2026-11-13 ·Tianhang Lu, Runtian Ren, Shengcai Liu
theory similarity 0.64
Abstract

We determine the dense worst-case quantum query complexity of exact minimum multicut on simple unweighted undirected graphs. With at most $k$ explicit demand pairs, our adjacency-array algorithm uses $\OO(n+\min\{m,n^{3/2}\sqrt{k}\})$ queries; a matching lower bound holds for every $1\le k\le\lfloor n/2\rfloor$ and sufficiently large $n$, with constants uniform in $k$. In particular, the $k=1$ case gives an $\OO(n^{3/2})$ query algorithm for prescribed $s$--$t$ cut. The upper bound combines degree-sensitive spectral estimates of local improvement with refinement by unions of label classes. These steps retain every original optimum and permit exact acquisition without an additional label-count factor. Separately, we prove an $Ω(n^{3/2})$ global minimum-cut lower bound on dense connected graphs, matching the existing upper bound up to polylogarithmic factors. It holds for the value and for any optimum shore, even with known degrees and sorted neighbor arrays; regular hard instances have balanced optimum cuts. Both lower bounds use degree-preserving switches and classify optimum outputs across a hidden threshold. Our upper bound concerns input queries, not total running time: computation on acquired data may be exponential, even in the single-demand case. Matching bounds at each prescribed sparse edge count are not established.

0.12