Forward and Backward Constrained Bisimulations for Quantum Circuits using Decision Diagrams

• URL: http://arxiv.org/abs/2308.09510v6
• Date: Fri, 10 May 2024 12:04:51 GMT
• Title: Forward and Backward Constrained Bisimulations for Quantum Circuits using Decision Diagrams
• Authors: Lukas Burgholzer, Antonio Jiménez-Pastor, Kim G. Larsen, Mirco Tribastone, Max Tschaikowski, Robert Wille,
• Abstract summary: We develop efficient methods for the simulation of quantum circuits on classic computers. In particular, we show that constrained bisimulation can boost decision-diagram-based quantum circuit simulation by several orders of magnitude.
• Score: 3.788308836856851
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Efficient methods for the simulation of quantum circuits on classic computers are crucial for their analysis due to the exponential growth of the problem size with the number of qubits. Here we study lumping methods based on bisimulation, an established class of techniques that has been proven successful for (classic) stochastic and deterministic systems such as Markov chains and ordinary differential equations. Forward constrained bisimulation yields a lower-dimensional model which exactly preserves quantum measurements projected on a linear subspace of interest. Backward constrained bisimulation gives a reduction that is valid on a subspace containing the circuit input, from which the circuit result can be fully recovered. We provide an algorithm to compute the constraint bisimulations yielding coarsest reductions in both cases, using a duality result relating the two notions. As applications, we provide theoretical bounds on the size of the reduced state space for well-known quantum algorithms for search, optimization, and factorization. Using a prototype implementation, we report significant reductions on a set of benchmarks. In particular, we show that constrained bisimulation can boost decision-diagram-based quantum circuit simulation by several orders of magnitude, allowing thus for substantial synergy effects.

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)
• Scaling Up the Quantum Divide and Conquer Algorithm for Combinatorial Optimization [0.8121127831316319]
  We propose a method for constructing quantum circuits which greatly reduces inter-device communication costs. We show that we can construct tractable circuits nearly three times the size of previous QDCA methods while retaining a similar or greater level of quality.
  arXiv  Detail & Related papers  (2024-05-01T20:49:50Z)
• Improved Quantum Algorithms for Eigenvalues Finding and Gradient Descent [0.0]
  Block encoding is a key ingredient in the recently developed quantum signal processing that forms a unifying framework for quantum algorithms. In this article, we utilize block encoding to substantially enhance two previously proposed quantum algorithms. We show how to extend our proposed method to different contexts, including matrix inversion and multiple eigenvalues estimation.
  arXiv  Detail & Related papers  (2023-12-22T15:59:03Z)
• Minimizing the negativity of quantum circuits in overcomplete quasiprobability representations [0.6428333375712125]
  We develop an approach for minimizing the total negativity of a given quantum circuit with respect to quasiprobability representations, that are overcomplete. Our approach includes both optimization over equivalent quasistochastic vectors and matrices, which appear due to the overcompleteness. We also study the negativity minimization of noisy brick-wall random circuits via a combination of increasing frame dimension and applying gate merging technique.
  arXiv  Detail & Related papers  (2023-06-19T08:02:00Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  tensor network (TN) algorithms can be mapped to parametrized quantum circuits (PQCs) We propose a new protocol for approximating TN states using realistic quantum circuits. Our results reveal one particular protocol, involving sequential growth and optimization of the quantum circuit, to outperform all other methods.
  arXiv  Detail & Related papers  (2022-09-01T17:08:41Z)
• Bayesian Learning of Parameterised Quantum Circuits [0.0]
  We take a probabilistic point of view and reformulate the classical optimisation as an approximation of a Bayesian posterior. We describe a dimension reduction strategy based on a maximum a posteriori point estimate with a Laplace prior. Experiments on the Quantinuum H1-2 computer show that the resulting circuits are faster to execute and less noisy than circuits trained without a gradient.
  arXiv  Detail & Related papers  (2022-06-15T14:20:14Z)
• Numerical Simulations of Noisy Quantum Circuits for Computational Chemistry [51.827942608832025]
  Near-term quantum computers can calculate the ground-state properties of small molecules. We show how the structure of the computational ansatz as well as the errors induced by device noise affect the calculation.
  arXiv  Detail & Related papers  (2021-12-31T16:33:10Z)
• Quantum amplitude damping for solving homogeneous linear differential equations: A noninterferometric algorithm [0.0]
  This work proposes a novel approach by using the Quantum Amplitude Damping operation as a resource, in order to construct an efficient quantum algorithm for solving homogeneous LDEs. We show that such an open quantum system-inspired circuitry allows for constructing the real exponential terms in the solution in a non-interferometric.
  arXiv  Detail & Related papers  (2021-11-10T11:25:32Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• 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)

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.