Quadratic Sums-of-Powers for Fixed-Parameter Tractable Quantum-Circuit Simulation

• URL: http://arxiv.org/abs/2605.29944v1
• Date: Thu, 28 May 2026 13:54:42 GMT
• Title: Quadratic Sums-of-Powers for Fixed-Parameter Tractable Quantum-Circuit Simulation
• Abstract summary: We show that the structural quantity most accurately governing the difficulty is the rank-width of the path-variable graph.<n>We give an algorithm that evaluates the amplitude in time that is exponential only in this rank-width and in the circuit size.<n>New method applies to every circuit built from Hadamard and diagonal gates, in particular to circuits over Clifford+T.
• Score: 17.91644278251664
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Strongly simulating a quantum circuit, that is, computing an output amplitude, amounts to summing the circuit's Feynman paths, a weighted count over assignments to the Boolean ``path'' variables. The circuit's gates induce correlations among these variables, forming a graph whose structure determines the hardness of the simulation task. This sum-of-powers viewpoint underlies recent simulators built on knowledge-representation tools from artificial intelligence, namely binary decision diagrams and weighted model counting. We show that the structural quantity most accurately governing the difficulty is the rank-width of the path-variable graph, and we give an algorithm that evaluates the amplitude in time that is exponential only in this rank-width and polynomial in the circuit size. Rank-width can be far smaller than the widths that control competing methods: as corollaries, our algorithm reproduces a recent decision-diagram simulation breakthrough as a special case and matches the Markov--Shi tensor-network contraction bound. To complement this, we exhibit circuit families on which our algorithm provably beats both competing methods. The new method applies to every circuit built from Hadamard and diagonal gates, in particular to circuits over Clifford+T. In practical terms, general-purpose decision-diagram and model-counting tools can serve as the workhorse, with our specialized algorithm dispatched to exploit a small rank-width of the associated graph when it is present.

Related papers

• Breaking the Treewidth Barrier in Quantum Circuit Simulation with Decision Diagrams [8.586836962892443]
  This work rigorously analyzes FeynmanDD, a decision diagram-based simulation method proposed in CAV 2025 by a subset of the authors.<n>We show that the method remains efficient if we use the Solovay-Kitaev algorithm to expand arbitrary single-qubit gates to sequences of Hadamard and T gates.
  arXiv  Detail & Related papers  (2025-10-08T08:58:58Z)
• Optimizing Quantum Circuits via ZX Diagrams using Reinforcement Learning and Graph Neural Networks [38.499527873574436]
  We introduce a framework based on ZX calculus, graph-neural networks and reinforcement learning for quantum circuit optimization.<n>By combining reinforcement learning and tree search, our method addresses the challenge of selecting optimal sequences of ZX calculus rewrite rules.<n>We demonstrate our method's competetiveness with state-of-the-art circuit generalizations and capabilities on large sets of diverse random circuits.
  arXiv  Detail & Related papers  (2025-04-04T13:19:08Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Automatically Identifying Local and Global Circuits with Linear Computation Graphs [45.760716193942685]
  We introduce our circuit discovery pipeline with Sparse Autoencoders (SAEs) and a variant called Transcoders. Our methods do not require linear approximation to compute the causal effect of each node. We analyze three kinds of circuits in GPT-2 Small: bracket, induction, and Indirect Object Identification circuits.
  arXiv  Detail & Related papers  (2024-05-22T17:50:04Z)
• Simulation of Graph Algorithms with Looped Transformers [6.0465914748433915]
  We study the ability of transformer networks to simulate algorithms on graphs from a theoretical perspective. We prove by construction that this architecture can simulate individual algorithms such as Dijkstra's shortest path. We show a Turing Completeness result with constant width when the extra attention heads are utilized.
  arXiv  Detail & Related papers  (2024-02-02T02:48:03Z)
• Unified framework for efficiently computable quantum circuits [0.0]
  Quantum circuits consisting of Clifford and matchgates are two classes of circuits that are known to be efficiently simulatable on a classical computer. We introduce a unified framework that shows in a transparent way the special structure that allows these circuits can be efficiently simulatable.
  arXiv  Detail & Related papers  (2024-01-16T08:04:28Z)
• Tensor Networks or Decision Diagrams? Guidelines for Classical Quantum Circuit Simulation [65.93830818469833]
  tensor networks and decision diagrams have independently been developed with differing perspectives, terminologies, and backgrounds in mind. We consider how these techniques approach classical quantum circuit simulation, and examine their (dis)similarities with regard to their most applicable abstraction level. We provide guidelines for when to better use tensor networks and when to better use decision diagrams in classical quantum circuit simulation.
  arXiv  Detail & Related papers  (2023-02-13T19:00:00Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  Quantum computing can empower machine learning models by enabling kernel machines to leverage quantum kernels for representing similarity measures between data.<n>We present an approach to this problem, which employs optimization techniques, similar to those used in neural architecture search and AutoML.<n>The results obtained by testing our approach on a high-energy physics problem demonstrate that, in the best-case scenario, we can either match or improve testing accuracy with respect to the manual design approach.
  arXiv  Detail & Related papers  (2022-09-22T16:42:14Z)
• Constructing Optimal Contraction Trees for Tensor Network Quantum Circuit Simulation [1.2704529528199062]
  One of the key problems in quantum circuit simulation is the construction of a contraction tree. We introduce a novel time algorithm for constructing an optimal contraction tree. We show that our method achieves superior results on a majority of tested quantum circuits.
  arXiv  Detail & Related papers  (2022-09-07T02:50:30Z)
• Simulation Paths for Quantum Circuit Simulation with Decision Diagrams [72.03286471602073]
  We study the importance of the path that is chosen when simulating quantum circuits using decision diagrams. We propose an open-source framework that allows to investigate dedicated simulation paths.
  arXiv  Detail & Related papers  (2022-03-01T19:00:11Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• Machine Learning Optimization of Quantum Circuit Layouts [63.55764634492974]
  We introduce a quantum circuit mapping, QXX, and its machine learning version, QXX-MLP. The latter infers automatically the optimal QXX parameter values such that the layed out circuit has a reduced depth. We present empiric evidence for the feasibility of learning the layout method using approximation.
  arXiv  Detail & Related papers  (2020-07-29T05:26:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.