Towards Efficient Verification of Computation in Quantum Devices

• URL: http://arxiv.org/abs/2508.00262v1
• Date: Fri, 01 Aug 2025 02:10:06 GMT
• Title: Towards Efficient Verification of Computation in Quantum Devices
• Authors: Keren Li, Peng Yan, Hanru Jiang, Nengkun Yu,
• Abstract summary: Traditional methods of comprehensively verifying quantum devices, such as quantum process tomography, face significant limitations because of the exponential growth in computational resources.<n>In this paper, we investigate the structure of computations on the hardware, focusing on the layered interruptible quantum circuit model.<n>Our method completely reconstructs the circuits within a time complexity of $O(d2 t log (n/delta))$, guaranteeing success with a probability of at least $1-delta$.<n>Our approach significantly reduces execution time for completely verifying computations in quantum devices, achieving double logarithmic scaling in the problem size.
• Score: 12.146871607856037
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Designing quantum processors is a complex task that demands advanced verification methods to ensure their correct functionality. However, traditional methods of comprehensively verifying quantum devices, such as quantum process tomography, face significant limitations because of the exponential growth in computational resources. These limitations arise from treating the system as a black box and ignoring its design structure. Consequently, new testing methods must be developed considering the design structure. In this paper, we investigate the structure of computations on the hardware, focusing on the layered interruptible quantum circuit model and designing a scalable algorithm to verify it comprehensively. Specifically, for a given quantum hardware that claims to process an unknown $n$ qubit $d$ layer circuit via a finite set of quantum gates, our method completely reconstructs the circuits within a time complexity of $O(d^2 t \log (n/\delta))$, guaranteeing success with a probability of at least $1-\delta$. Here, $t$ represents the maximum execution time for each circuit layer. Our approach significantly reduces execution time for completely verifying computations in quantum devices, achieving double logarithmic scaling in the problem size. Furthermore, we validate our algorithm through experiments using IBM's quantum cloud service, demonstrating its potential applicability in the noisy intermediate-scale quantum era.

Related papers

• Q-Fusion: Diffusing Quantum Circuits [2.348041867134616]
  We propose a diffusion-based algorithm leveraging the LayerDAG framework to generate new quantum circuits.<n>Our results demonstrate that the proposed model consistently generates 100% valid quantum circuit outputs.
  arXiv  Detail & Related papers  (2025-04-29T14:10:10Z)
• 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)
• 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)
• Route-Forcing: Scalable Quantum Circuit Mapping for Scalable Quantum Computing Architectures [41.39072840772559]
  Route-Forcing is a quantum circuit mapping algorithm that shows an average speedup of $3.7times$. We present a quantum circuit mapping algorithm that shows an average speedup of $3.7times$ compared to the state-of-the-art scalable techniques.
  arXiv  Detail & Related papers  (2024-07-24T14:21:41Z)
• Quantum Compiling with Reinforcement Learning on a Superconducting Processor [55.135709564322624]
  We develop a reinforcement learning-based quantum compiler for a superconducting processor. We demonstrate its capability of discovering novel and hardware-amenable circuits with short lengths. Our study exemplifies the codesign of the software with hardware for efficient quantum compilation.
  arXiv  Detail & Related papers  (2024-06-18T01:49:48Z)
• A multiple-circuit approach to quantum resource reduction with application to the quantum lattice Boltzmann method [39.671915199737846]
  We introduce a multiple-circuit algorithm for a quantum lattice Boltzmann method (QLBM) solve of the incompressible Navier--Stokes equations.<n>The presented method is validated and demonstrated for 2D lid-driven cavity flow.
  arXiv  Detail & Related papers  (2024-01-20T15:32:01Z)
• 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)
• QuBEC: Boosting Equivalence Checking for Quantum Circuits with QEC Embedding [4.15692939468851]
  We propose a Decision Diagram-based quantum equivalence checking approach, QuBEC, that requires less latency compared to existing techniques. Our proposed methodology reduces verification time on certain benchmark circuits by up to $271.49 times$.
  arXiv  Detail & Related papers  (2023-09-19T16:12:37Z)
• $T$-depth-optimized Quantum Search with Quantum Data-access Machine [0.0]
  We introduce an efficient quantum data-access process, dubbed as quantum data-access machine (QDAM) We analyze the runtime of our algorithm in view of the fault-tolerant quantum computation (FTQC) consisting of logical qubits within an effective quantum error correction code.
  arXiv  Detail & Related papers  (2022-11-08T01:36:02Z)
• Quantum circuit debugging and sensitivity analysis via local inversions [62.997667081978825]
  We present a technique that pinpoints the sections of a quantum circuit that affect the circuit output the most. We demonstrate the practicality and efficacy of the proposed technique by applying it to example algorithmic circuits implemented on IBM quantum machines.
  arXiv  Detail & Related papers  (2022-04-12T19:39:31Z)
• Low-rank quantum state preparation [1.5427245397603195]
  We propose an algorithm to reduce state preparation circuit depth by offloading computational complexity to a classical computer. We show that the approximation is better on today's quantum processors.
  arXiv  Detail & Related papers  (2021-11-04T19:56:21Z)
• Long-Time Error-Mitigating Simulation of Open Quantum Systems on Near Term Quantum Computers [38.860468003121404]
  We study an open quantum system simulation on quantum hardware, which demonstrates robustness to hardware errors even with deep circuits containing up to two thousand entangling gates. We simulate two systems of electrons coupled to an infinite thermal bath: 1) a system of dissipative free electrons in a driving electric field; and 2) the thermalization of two interacting electrons in a single orbital in a magnetic field -- the Hubbard atom. Our results demonstrate that algorithms for simulating open quantum systems are able to far outperform similarly complex non-dissipative algorithms on noisy hardware.
  arXiv  Detail & Related papers  (2021-08-02T21:36:37Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  Variational quantum algorithms are believed to be promising for solving computationally hard problems. In this paper, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
  arXiv  Detail & Related papers  (2020-05-11T17:20:51Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling. We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
  arXiv  Detail & Related papers  (2020-05-05T20:11:53Z)
• Demonstrating NISQ Era Challenges in Algorithm Design on IBM's 20 Qubit Quantum Computer [0.0]
  We present results from experiments run on IBM's 20-qubit Poughkeepsie' architecture. Results demonstrate various qubit qualities and challenges that arise in designing quantum algorithms.
  arXiv  Detail & Related papers  (2020-03-02T16:36:33Z)

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.