Simulating Quantum Circuits by Model Counting

• URL: http://arxiv.org/abs/2403.07197v1
• Date: Mon, 11 Mar 2024 22:40:15 GMT
• Title: Simulating Quantum Circuits by Model Counting
• Authors: Jingyi Mei, Marcello Bonsangue and Alfons Laarman
• Abstract summary: We show for the first time that a strong simulation of universal quantum circuits can be efficiently tackled through weighted model counting. Our work paves the way to apply the existing array of powerful classical reasoning tools to realize efficient quantum circuit compilation.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum circuit compilation comprises many computationally hard reasoning tasks that nonetheless lie inside #$\mathbf{P}$ and its decision counterpart in $\mathbf{PP}$. The classical simulation of general quantum circuits is a core example. We show for the first time that a strong simulation of universal quantum circuits can be efficiently tackled through weighted model counting by providing a linear encoding of Clifford+T circuits. To achieve this, we exploit the stabilizer formalism by Knill, Gottesmann, and Aaronson and the fact that stabilizer states form a basis for density operators. With an open-source simulator implementation, we demonstrate empirically that model counting often outperforms state-of-the-art simulation techniques based on the ZX calculus and decision diagrams. Our work paves the way to apply the existing array of powerful classical reasoning tools to realize efficient quantum circuit compilation; one of the obstacles on the road towards quantum supremacy.

Related papers

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Bridging Classical and Quantum: Group-Theoretic Approach to Quantum Circuit Simulation [0.0]
  Efficiently simulating quantum circuits on classical computers is a fundamental challenge in quantum computing. This paper presents a novel theoretical approach that achieves exponential speedups (polynomial runtime) over existing simulators. The findings may have implications for quantum algorithm design, error correction, and the development of more efficient quantum simulators.
  arXiv  Detail & Related papers  (2024-07-28T20:02:21Z)
• 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)
• Mapping quantum circuits to shallow-depth measurement patterns based on graph states [0.0]
  We create a hybrid simulation technique for measurement-based quantum computing. We show that groups of fully commuting operators can be implemented using fully-parallel, i.e., non-adaptive, measurements. We discuss how such circuits can be implemented in constant quantum depths by employing quantum teleportation.
  arXiv  Detail & Related papers  (2023-11-27T19:00:00Z)
• 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)
• A Reorder Trick for Decision Diagram Based Quantum Circuit Simulation [0.4358626952482686]
  We study two classes of quantum circuits on which the state-of-the-art decision diagram based simulators failed to perform well in terms of simulation time. We propose a simple and powerful reorder trick to boost the simulation of such quantum circuits.
  arXiv  Detail & Related papers  (2022-11-14T04:55:25Z)
• Tensor Network Quantum Virtual Machine for Simulating Quantum Circuits at Exascale [57.84751206630535]
  We present a modernized version of the Quantum Virtual Machine (TNQVM) which serves as a quantum circuit simulation backend in the e-scale ACCelerator (XACC) framework. The new version is based on the general purpose, scalable network processing library, ExaTN, and provides multiple quantum circuit simulators. By combining the portable XACC quantum processors and the scalable ExaTN backend we introduce an end-to-end virtual development environment which can scale from laptops to future exascale platforms.
  arXiv  Detail & Related papers  (2021-04-21T13:26:42Z)
• 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)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)
• Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
  Random quantum circuits are commonly viewed as hard to simulate classically. We show that approximate simulation of typical instances is almost as hard as exact simulation. We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
  arXiv  Detail & Related papers  (2019-12-31T19:00:00Z)

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.