Traq: Estimating the Quantum Cost of Classical Programs

• URL: http://arxiv.org/abs/2509.01508v1
• Date: Mon, 01 Sep 2025 14:28:49 GMT
• Title: Traq: Estimating the Quantum Cost of Classical Programs
• Authors: Anurudh Peduri, Gilles Barthe, Michael Walter,
• Abstract summary: Traq is a principled approach towards estimating the quantum speedup of classical programs.<n>It consists of a classical language that includes high-level primitives amenable to quantum speedups, a cost analysis, and a compilation to low-level quantum programs.
• Score: 6.4091903997670245
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Predicting practical speedups offered by future quantum computers has become a major focus of the quantum computing community. Typically, these predictions are supported by lengthy manual analyses and numerical simulations and are carried out for one specific application at a time. In this paper, we present Traq, a principled approach towards estimating the quantum speedup of classical programs fully automatically and with provable guarantees. It consists of a classical language that includes high-level primitives amenable to quantum speedups, a cost analysis, and a compilation to low-level quantum programs. Our cost analysis upper bounds the complexity of the resulting quantum program in a fine-grained way: it captures non-asymptotic information and is sensitive to the input of the program (rather than providing worst-case costs). We also provide a proof-of-concept implementation and a case study inspired by AND-OR trees.

Related papers

• Digital quantum simulation of many-body systems: Making the most of intermediate-scale, noisy quantum computers [51.56484100374058]
  This thesis is centered around simulating quantum dynamics on quantum devices.<n>We present an overview of the most relevant quantum algorithms for quantum dynamics.<n>We identify relevant problems within quantum dynamics that could benefit from quantum simulation in the near future.
  arXiv  Detail & Related papers  (2025-08-29T10:37:19Z)
• The Road to Hybrid Quantum Programs: Characterizing the Evolution from Classical to Hybrid Quantum Software [3.1240846678117546]
  Efforts to identify quantum candidate code fragments that can meaningfully execute on quantum machines primarily rely on static code analysis.<n>This paper aims to systematically formalize the process of identifying quantum candidates and their proper encoding within classical programs.
  arXiv  Detail & Related papers  (2025-03-14T14:37:57Z)
• Quantum Computer Does Not Need Coherent Quantum Access for Advantage [0.0]
  A majority of quantum speedups rely on a subroutine in which classical information can be accessed in a coherent quantum manner.<n>We develop a quantum gradient descent algorithm for optimization, which is a fundamental technique that enjoys a wide range of applications.
  arXiv  Detail & Related papers  (2025-03-04T11:24:28Z)
• Benchmarking quantum devices beyond classical capabilities [1.2499537119440245]
  The Quantum Volume (QV) test is one of the most widely used benchmarks for evaluating quantum computer performance.<n>We propose modifications of the QV test that allow for direct determination of the most probable outcomes.
  arXiv  Detail & Related papers  (2025-02-04T18:50:47Z)
• QCircuitBench: A Large-Scale Dataset for Benchmarking Quantum Algorithm Design [63.02824918725805]
  Quantum computing is recognized for the significant speedup it offers over classical computing through quantum algorithms.<n>QCircuitBench is the first benchmark dataset designed to evaluate AI's capability in designing and implementing quantum algorithms.
  arXiv  Detail & Related papers  (2024-10-10T14:24:30Z)
• On Reducing the Execution Latency of Superconducting Quantum Processors via Quantum Job Scheduling [47.39648643132327]
  We introduce the Quantum Job Scheduling Problem (QJSP) to improve the utility efficiency of quantum resources.<n>We propose a noise-aware quantum job scheduler (NAQJS) concerning the circuit width, number of measurement shots, and submission time of quantum jobs.<n>We conduct extensive experiments on a simulated Qiskit noise model, as well as on the Xiaohong (from QuantumCTek) superconducting quantum processor.
  arXiv  Detail & Related papers  (2024-04-11T16:12:01Z)
• A Quantum-Classical Collaborative Training Architecture Based on Quantum State Fidelity [50.387179833629254]
  We introduce a collaborative classical-quantum architecture called co-TenQu. Co-TenQu enhances a classical deep neural network by up to 41.72% in a fair setting. It outperforms other quantum-based methods by up to 1.9 times and achieves similar accuracy while utilizing 70.59% fewer qubits.
  arXiv  Detail & Related papers  (2024-02-23T14:09:41Z)
• Realistic Runtime Analysis for Quantum Simplex Computation [0.4407851469168588]
  We present a quantum analog for classical runtime analysis when solving real-world instances of important optimization problems. We show that a practical quantum advantage for realistic problem sizes would require quantum gate operation times that are considerably below current physical limitations.
  arXiv  Detail & Related papers  (2023-11-16T16:11:44Z)
• Quantum Machine Learning: from physics to software engineering [58.720142291102135]
  We show how classical machine learning approach can help improve the facilities of quantum computers. We discuss how quantum algorithms and quantum computers may be useful for solving classical machine learning tasks.
  arXiv  Detail & Related papers  (2023-01-04T23:37:45Z)
• Hunting for quantum-classical crossover in condensed matter problems [0.3799859284309834]
  We propose a systematic error/runtime analysis on state-of-the-art classical algorithm based on tensor networks. We argue that condensed matter problems offer the earliest platform for demonstration of practical quantum advantage.
  arXiv  Detail & Related papers  (2022-10-25T15:50:54Z)
• Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
  We present an approach where the quantum computation is supplemented by a classical result. Taking advantage of its anticipation also leads to a new type of quantum measurements, which we call anticipative. In an anticipative quantum measurement the combination of the results from classical and quantum computations happens only in the end.
  arXiv  Detail & Related papers  (2022-09-12T15:47:44Z)
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage [43.3054117987806]
  We introduce a scalable procedure for harnessing classical computing resources to provide pre-optimized initializations for quantum circuits. We show this method significantly improves the trainability and performance of PQCs on a variety of problems. By demonstrating a means of boosting limited quantum resources using classical computers, our approach illustrates the promise of this synergy between quantum and quantum-inspired models in quantum computing.
  arXiv  Detail & Related papers  (2022-08-29T15:24:03Z)
• Advancing Hybrid Quantum-Classical Computation with Real-Time Execution [10.818632836746668]
  We describe a next-generation implementation of classical computation embedded within quantum programs. It enables the real-time calculation and adjustment of program variables based on the mid-circuit state of measured qubits.
  arXiv  Detail & Related papers  (2022-06-26T19:50:15Z)
• On exploring the potential of quantum auto-encoder for learning quantum systems [60.909817434753315]
  We devise three effective QAE-based learning protocols to address three classically computational hard learning problems. Our work sheds new light on developing advanced quantum learning algorithms to accomplish hard quantum physics and quantum information processing tasks.
  arXiv  Detail & Related papers  (2021-06-29T14:01:40Z)

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.