CS Paper Radar

Polynomial-time local-unitary equivalence of graph states

Yuxuan Zhang

cs.CC quant-phcond-mat.mtrl-sci ·submitted 2026-09-30 18:15 UTC · v2

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Clifford synthesis is NP-complete

cs.CC quant-ph ·2026-10-29 ·Søren Fuglede Jørgensen
similarity 0.71
Abstract

We show that the problem of synthesizing a quantum circuit for a given Clifford operator using at most a specified amount of resources is NP-complete for several resource models of practical interest. Specifically, we study synthesis of a given Clifford operator using single-qubit Clifford gates and two-qubit Clifford gates, with full qubit connectivity and no additional ancilla qubits. With single-qubit gates free and CNOT as the only two-qubit gate, we show that deciding whether a given target admits an implementation using at most a specified number of CNOT gates is NP-complete, and we show that the problem remains NP-complete when any two-qubit Clifford gate is allowed and the budget counts all such gates. Moreover, we show that both results continue to hold when SWAP gates may be inserted for free, and when single-qubit gates are also considered part of the budget. In each case, we build on recent work by Li and Guan and show that there are polynomial-time reductions from Hamiltonian path in grid graphs to these decision problems, using a number of qubits quadratic in the number of grid vertices.

0.05

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.70
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.34

Hidden Circuits and Exact Counting in Ordered Graphs

cs.CC cs.DS ·2026-09-16 ·Chenghua Liu, Boning Meng
theory similarity 0.69
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).

0.21

A Dichotomy for Exact Quantum Circuit Amplitudes

cs.CC ·2026-11-17 ·Chenghua Liu, Boning Meng
similarity 0.69
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.17

A Grover-Amplified Oracle for Maximum Clique on Graph, Minimum Hitting set and Dualizations on Hypergraphs Built on Quantum Phase Estimation

cs.CC quant-ph ·2026-11-07 ·Francisco Piñero, Fernando L. \Pelayo, Hernan I. de la Cruz, Jose J. Paulet, Mauro Mezzini +1 more
similarity 0.68
Abstract

In this paper, we use a quantum circuit called the Graph Encoding Operator which, applied to the complement $\bar G$ of any graph $G$, yields an oracle for the maximum clique problem suitable for amplification via Grover's algorithm. Analogously, we devise a Hypergraph Encoding Operator which, when applied to a hypergraph $\mathcal H$, yields an oracle for the minimum hitting set suitable for amplification via Grover's algorithm. Interestingly, the latter oracle provides, when measured, an approximation of the number of hitting sets of the hypergraph, thus solving the dualization problem for positive Boolean functions represented in a positive irredundant disjunctive normal form. We give the full construction of both operators, prove their correctness, analyze their complexity, and provide an implementation on a quantum simulator. We discuss the resulting complexity, contrast them with existing quantum computer algorithms based on Grover search and we will show that our algorithms outperform, to the best of our knowledge, all of the previous algorithms on space computational complexity by requiring only $O(N)$ number of qubits with respect to the number of vertices $N$, for representing both graphs and hypergraphs in the encoding operator and, consequently, results in an oracle for both graphs and hypergraphs that uses only $O(N)$ qubits even when the hypergraph contains an exponential (on the number of vertices) number of hyperedges.

0.29

A Quantum Lower Bound for Triangle Finding

cs.DS quant-ph ·2026-11-04 ·Arjan Cornelissen, Amin Shiraz Gilani, Xingyu Zhou
theory similarity 0.66
Abstract · 37 pages

Triangle finding is a fundamental problem in graph theory that has played a central role in the development of quantum algorithmic techniques. For $N$-vertex graphs given by their adjacency matrices, a long line of work has improved the quantum query upper bound from $O(N^{3/2})$ to $O(N^{5/4})$. However, the best known lower bound has remained the elementary $Ω(N)$ bound obtained from unstructured search. We prove the first superlinear quantum query lower bound for triangle finding, showing that $Ω(N^{13/12})$ queries are necessary. Our result also implies the same lower bound for triangle detection and for detecting every fixed connected non-bipartite graph. The proof builds on the compressed oracle approach of Zhandry and the transfer approaches of Belovs. It compares the computation on graphs with a planted triangle to the computation on random graphs conditioned to be triangle-free, through a map on the input registers that almost commutes with every query. We average over local changes to the input while preserving its distribution, through a procedure known as conditional resampling. Our main technical contribution is a set of estimates that let us control the query error under this averaging, despite the dependence introduced by conditioning a dense graph to be triangle-free.

0.48

Complexity separations for optimal matchgate-Clifford synthesis

cs.CC quant-ph ·2026-10-05 ·Berta Casas, Diego García-Martín, Yuxuan Zhang
benchmarktheory similarity 0.66
Abstract · 20 + 21 pages, 4 + 1 figures

Clifford and matchgate circuits are canonical families of classically simulable quantum circuits. Their intersection, the matchgate-Clifford group, plays an important role in randomized fermionic protocols and in matchgate synthesis. Its adjoint action is isomorphic to the group of unit-determinant signed permutations of $2n$ Majorana modes, and we study optimal exact synthesis in this group. That is, given a target unitary and a gate set, output an $n$-qubit circuit implementing the target using the fewest operations. We show that the complexity of this problem strongly depends on the gate set. In particular, we study gate sets consisting of Majorana braids with different connectivity graphs. For path and complete graphs, we prove that the problem is classically solvable in $\mathcal{O}\left(n^2\right)$ time, and we provide explicit gate-optimal compilers. In addition, we prove that when the connectivity graph is a tree, the decision version of the optimal synthesis problem becomes NP-complete. Finally, we benchmark our optimal compiler on chains of up to $n=80$ qubits against those of \texttt{Qiskit} and \texttt{Tket}, obtaining circuits with constant factor improvements $\times2.57$ and $\times2.28$ in the total number of gates, respectively.

0.38

Planted Cliques and Quantum Symmetry-Adapted Measurements

cs.CC quant-ph ·2026-09-30 ·Vojtech Havlicek, Jordan Docter, Subhash Khot
theory similarity 0.65
Abstract · 21 pages, no figures. Revised it to improve clarity and readability. VH takes responsibility for the previous submission prepared under a ti…

We study how quantum encodings and symmetry-adapted measurements preserve information for planted-clique detection from one classical graph. For $k=\lfloor n^{1/2-\varepsilon}\rfloor$, with fixed $0<\varepsilon<1/2$, detection is statistically possible but conjectured hard for polynomial-time classical algorithms. For a compact binary phase encoding, we prove that constant-advantage detection requires $Ω(n^{1+2\varepsilon}\ln^2 n)$ copies of the phase state of the same graph, even under arbitrary joint measurements. In the large-copy limit, the optimal decision rule thresholds the total number of $k$-cliques in the graph and its complement, but this characterization provides no efficient detector. We therefore explore measurements guided by the symmetries of the input distributions, starting with the efficient Schur transform on the full graph register. We show that weak Schur sampling, which measures only the representation label, depends only on edge count and has vanishing distinguishing power in this regime. When the label and multiplicity registers are discarded, the remaining quantum states are almost perfectly distinguishable. We show that the support of the planted state occupies only a vanishing fraction of the graph Hilbert space. Any subspace containing it still permits near-perfect detection if its relative dimension also vanishes. This gives us freedom to choose a subspace that is easier to measure. We propose exploring subgroup isotypic measurements to find such subspaces. Whether they can yield an efficient detector remains open. Finally, we show that a single supplied coherent quantum sample permits efficient detection, yielding a conditional computational separation from one classical sample under quantum planted-clique hardness.

0.32