arXiv:1412.0625

Quipper: Concrete Resource Estimation in Quantum Algorithms

Jonathan M. Smith, Neil J. Ross, Peter Selinger, Benoît Valiron

Published Dec 1, 2014• 10 citations

Abstract

Despite the rich literature on quantum algorithms, there is a surprisingly small amount of coverage of their concrete logical design and implementation. Most resource estimation is done at the level of complexity analysis, but actual concrete numbers (of quantum gates, qubits, etc.) can differ by orders of magnitude. The line of work we present here is a formal framework to write, and reason about, quantum algorithms. Specifically, we designed a language, Quipper, with scalability in mind, and we are able to report actual resource counts for seven non-trivial algorithms found in the quantum computer science literature.

DOI: 10.48550/arxiv.1412.0625

Related papers

Quipper

Alexander S. Green, Peter LeFanu Lumsdaine, Neil J. Ross +2 more

The field of quantum algorithms is vibrant. Still, there is currently a lack of programming languages for describing quantum computation on a practical scale, i.e., not just at the level of toy problems. We address this issue by introducing Quipper, a scalable, expressive, functional, higher-order quantum programming language. Quipper has been used to program a diverse set of non-trivial quantum algorithms, and can generate quantum gate representations using trillions of gates. It is geared towards a model of computation that uses a classical computer to control a quantum device, but is not dependent on any particular model of quantum hardware. Quipper has proven effective and easy to use, and opens the door towards using formal methods to analyze quantum algorithms.

ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)Jun 11, 2013333 citations

Quipper

Alexander S. Green, Peter LeFanu Lumsdaine, Neil J. Ross +2 more

arXiv:1304.3390ACM SIGPLAN NoticesJun 16, 2013156 citations

Counting Qubits and Gates: Resource Analysis in Quantum Programming Languages

Ugo Dal Lago

Quantum computing promises breakthroughs in solving complex problems faster than classical computing, thanks to quantum bits leveraging superposition and entanglement [18, 32]. Various models of quantum computation are being explored, including gate-based systems, quantum annealing [21], and topological quantum computing [22]. But how can such computational power be made available to the programmer in a way that makes the implementation of concrete algorithms and protocols straightforward?

International Symposium on Principles and Practice of Declarative Programming (PPDP)Sep 10, 20250 citations

Five reversible quantum gates in Quipper

Abdulwahab Alkharashi

Quipper is the most recently developed quantum programming language. In this work, we provide brief background information about Quipper and use its framework to demonstrate the implementation of five non-trivial reversible gates. Each gate works as a full adder gate. We will use a Quipper simulator to run a simulation for each gate on a classical computer.

Future Technologies ConferenceDec 1, 20160 citations

Resource Estimation for Fault-Tolerant Quantum Programs

Bonan Su, Yuan Feng, Li Zhou +1 more

Fault-tolerant quantum computation enables the deployment of practical quantum algorithms but incurs substantial overhead from error correction, making resource estimation a central concern. Beyond case-by-case analyses, existing quantum programming languages either require programmers to manipulate low-level hardware details, rendering fault-tolerant implementations cumbersome, or abstract away the underlying error-correction schemes, reducing the effectiveness of resource utilization and estimation. To address these limitations while preserving programmability, we present a quantum programming language that enables efficient resource utilization, together with a resource-estimation framework for comprehensive resource analysis. Our framework features programmer-visible abstractions of error-correction schemes and cross-layer program-hardware analysis, allowing systematic exploration of resource trade-offs. We evaluate our approach on detailed fault-tolerant implementations of practical large-scale quantum algorithms, including components typically treated as black boxes in existing frameworks. The results demonstrate that our framework enables substantial resource savings while delivering detailed, fine-grained, and accurate resource estimates for fault-tolerant quantum programs.

quant-pharXiv:2608.04573Aug 6, 20260 citations

On the importance of scalability and resource estimation of quantum algorithms for domain sciences

Vincent Richard Pascuzzi, Ning Bao, Ang Li

The quantum information science community has seen a surge in new algorithmic developments across scientific domains. These developments have demonstrated polynomial or better improvements in computational and space complexity, incentivizing further research in the field. However, despite recent progress, many works fail to provide quantitative estimates on algorithmic scalability or quantum resources required -- e.g., number of logical qubits, error thresholds, etc. -- to realize the highly sought "quantum advantage." In this paper, we discuss several quantum algorithms and motivate the importance of such estimates. By example and under simple scaling assumptions, we approximate the computational expectations of a future quantum device for a high energy physics simulation algorithm and how it compares to its classical analog. We assert that a standard candle is necessary for claims of quantum advantage.

arXiv:2205.00585May 2, 20220 citations