Node Replacement based Approximate Quantum Simulation with Decision Diagrams

• URL: http://arxiv.org/abs/2507.04335v1
• Date: Sun, 06 Jul 2025 10:44:36 GMT
• Title: Node Replacement based Approximate Quantum Simulation with Decision Diagrams
• Authors: Yexin Yan, Stefan Hillmich, Robert Wille, Christian Mayr,
• Abstract summary: We show how to do a trade-off between simulation accuracy and memory requirement in quantum circuits.<n>New approach achieves a better memory-accuracy trade-off for representing a quantum circuit with decision diagrams with minimal run time overhead.<n>For the first time, a strong better-than-linear trade-off between memory and fidelity is demonstrated for a decision diagram based quantum simulation.
• Score: 3.9656109301081557
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Simulating a quantum circuit with a classical computer requires exponentially growing resources. Decision diagrams exploit the redundancies in quantum circuit representation to efficiently represent and simulate quantum circuits. But for complicated quantum circuits like the quantum supremacy benchmark, there is almost no redundancy to exploit. Therefore, it often makes sense to do a trade-off between simulation accuracy and memory requirement. Previous work on approximate simulation with decision diagrams exploits this trade-off by removing less important nodes. In this work, instead of removing these nodes, we try to find similar nodes to replace them, effectively slowing down the fidelity loss when reducing the memory. In addition, we adopt Locality Sensitive Hashing (LSH) to drastically reduce the computational complexity for searching for replacement nodes. Our new approach achieves a better memory-accuracy trade-off for representing a quantum circuit with decision diagrams with minimal run time overhead. Notably, our approach shows good scaling properties when increasing the circuit size and depth. For the first time, a strong better-than-linear trade-off between memory and fidelity is demonstrated for a decision diagram based quantum simulation when representing the quantum supremacy benchmark circuits at high circuit depths, showing the potential of drastically reducing the resource requirement for approximate simulation of the quantum supremacy benchmarks on a classical computer.

Related papers

• Efficient Quantum Circuit Compilation for Near-Term Quantum Advantage [17.38734393793605]
  We propose an approximate method for compiling target quantum circuits into brick-wall layouts.<n>This new circuit design consists of two-qubit CNOT gates that can be directly implemented on real quantum computers.
  arXiv  Detail & Related papers  (2025-01-13T15:04:39Z)
• Variational Quantum Subspace Construction via Symmetry-Preserving Cost Functions [39.58317527488534]
  We propose a variational strategy based on symmetry-preserving cost functions to iteratively construct a reduced subspace for extraction of low-lying energy states.<n>As a proof of concept, we test the proposed algorithms on H4 chain and ring, targeting both the ground-state energy and the charge gap.
  arXiv  Detail & Related papers  (2024-11-25T20:33:47Z)
• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• FragQC: An Efficient Quantum Error Reduction Technique using Quantum Circuit Fragmentation [4.2754140179767415]
  We present it FragQC, a software tool that cuts a quantum circuit into sub-circuits when its error probability exceeds a certain threshold. We achieve an increase of fidelity by 14.83% compared to direct execution without cutting the circuit, and 8.45% over the state-of-the-art ILP-based method.
  arXiv  Detail & Related papers  (2023-09-30T17:38:31Z)
• Near-Term Distributed Quantum Computation using Mean-Field Corrections and Auxiliary Qubits [77.04894470683776]
  We propose near-term distributed quantum computing that involve limited information transfer and conservative entanglement production. We build upon these concepts to produce an approximate circuit-cutting technique for the fragmented pre-training of variational quantum algorithms.
  arXiv  Detail & Related papers  (2023-09-11T18:00:00Z)
• Forward and Backward Constrained Bisimulations for Quantum Circuits using Decision Diagrams [3.788308836856851]
  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.
  arXiv  Detail & Related papers  (2023-08-18T12:40:47Z)
• Quantivine: A Visualization Approach for Large-scale Quantum Circuit Representation and Analysis [31.203764035373677]
  We develop Quantivine, an interactive system for exploring and understanding quantum circuits. A series of novel circuit visualizations are designed to uncover contextual details such as qubit provenance, parallelism, and entanglement. The effectiveness of Quantivine is demonstrated through two usage scenarios of quantum circuits with up to 100 qubits.
  arXiv  Detail & Related papers  (2023-07-18T04:51: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)
• 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)
• Quantum compression with classically simulatable circuits [0.5735035463793007]
  We present a strategy to design quantum autoencoders using evolutionary algorithms for transforming quantum information into lower-dimensional representations. We successfully demonstrate the initial applications of the algorithm for compressing different families of quantum states. This approach opens the possibility of using classical logic to find low representations of quantum data, using fewer computational resources.
  arXiv  Detail & Related papers  (2022-07-06T20:36:10Z)
• Simulating the Mott transition on a noisy digital quantum computer via Cartan-based fast-forwarding circuits [62.73367618671969]
  Dynamical mean-field theory (DMFT) maps the local Green's function of the Hubbard model to that of the Anderson impurity model. Quantum and hybrid quantum-classical algorithms have been proposed to efficiently solve impurity models. This work presents the first computation of the Mott phase transition using noisy digital quantum hardware.
  arXiv  Detail & Related papers  (2021-12-10T17:32:15Z)
• 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)
• As Accurate as Needed, as Efficient as Possible: Approximations in DD-based Quantum Circuit Simulation [5.119310422637946]
  Decision Diagrams (DDs) have previously shown to reduce the required memory in many important cases by exploiting redundancies in the quantum state. We show that this reduction can be amplified by exploiting the probabilistic nature of quantum computers to achieve even more compact representations. Specifically, we propose two new DD-based simulation strategies that approximate the quantum states to attain more compact representations.
  arXiv  Detail & Related papers  (2020-12-10T12:02:03Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

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.