Source-linked AI summary
Quipper: A Scalable Quantum Programming Language
Alexander S. Green, Peter LeFanu Lumsdaine, Neil J. Ross, Peter Selinger, Benoît Valiron
TL;DR
Quantum algorithms lack programming languages that describe computation at practical scale. The paper introduces Quipper, a scalable functional language for expressing and generating quantum circuits, and demonstrates it on seven non-trivial algorithms, including circuits exceeding 30 trillion gates. Quipper is presented as usable and useful, while compile-time checking remains incomplete and the idealized hardware model may not match actual devices.
Problem
Quantum programming languages have lacked practical-scale support beyond toy algorithms, despite a vibrant quantum-algorithm field.
Method
Quipper combines a scalable functional language with classical control, circuit generation, dynamic lifting, and high-level circuit construction and manipulation.
Results
Quipper implemented seven non-trivial algorithms and generated a complete circuit exceeding 30 trillion gates using 4676 qubits.
Takeaways & Limitations
The authors conclude that Quipper is usable and useful for implementing algorithms at realistic problem sizes and supporting resource estimation.
Takeaways & Limitations
Compile-time checking remains incomplete because the language lacks a linear type system, so some quantum-data properties are checked at runtime.
Abstract
from arXiv · showhide
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.
1. Introduction
Quantum algorithms are advancing, but practical languages for expressing them remain limited. Quipper addresses this gap with a scalable, expressive language tested on seven non-trivial algorithms.
- Classical programming languages advanced computing by providing human-understandable abstractions and automated bookkeeping.
- Quantum algorithms can theoretically outperform classical computing for certain problem classes, and the field includes many recent algorithmic developments.
- Quipper is a declarative language with monadic operational semantics, designed to be succinct, expressive, scalable, and theoretically sound.
- Quipper’s scalability means going beyond toy algorithms and proof-of-concept programs, whose complexity exceeds earlier practical quantum languages.
- The paper implements seven non-trivial algorithms spanning graph search, formula evaluation, number theory, chemistry, linear systems, lattice problems, and triangle finding.
- Earlier quantum-language proposals include mostly theoretical formalisms, QCL, and functional languages that lack some combination of practical facilities, high-level data types, or advanced circuit features.
2. Quantum computation
Quantum computation stores information in quantum states and manipulates it through unitary operations and probabilistic measurement. The paper frames programming around classical control of quantum hardware while acknowledging that idealized models may not match physical devices.
- An idealized quantum device is described by its state and operations while ignoring physical imprecision and decoherence.
- A quantum state is a normalized Hilbert-space vector; unitary transformations manipulate it, while measurements extract classical information probabilistically.
- In the QRAM model, a classical computer controls a quantum co-processor through interleaved unitary operations and measurements on addressable qubits.
- Classical control flow and both classical and quantum data are first-class elements in the described computation model.
- Quantum programming languages must prevent nonphysical duplication of quantum information, either through compile-time or run-time checks.
- The QRAM model is not claimed to represent actual hardware, where short-lived states, error correction, timing constraints, and batch execution may matter.
- High-level languages should abstract from hardware-specific details and present users with a uniform idealized computational model.
3. Techniques used in quantum algorithms
Quantum algorithms are usually described above the level of individual gates, using reusable primitives, reversible oracles, and circuit-wide transformations. Their programs also combine parameterized circuit generation with classical control and execution.
- A useful quantum language should express algorithms at the abstraction level intended by their designers while filling in implementation details.
- Quantum Fourier transforms, amplitude amplification, and quantum walks are recurring building blocks that are often combined non-trivially.
- Classical oracle functions must be made reversible before being lifted into unitary operations on quantum bits.
- Quantum circuits are sequences of unitary gates with occasional measurements, but diagrams alone do not capture their parameter dependence.
- Algorithm descriptions commonly require reversing, iteration, oracle synthesis, ancilla management, circuit transformation, and whole-circuit optimization.
- Quantum programs typically use classical pre-processing, parameterized circuit generation, final measurement, and sometimes repeated or interleaved classical-quantum execution.
- A usable quantum language should integrate a general-purpose classical language with a distinct but seamless quantum component.
4. Our proposal: Quipper
Quipper is an embedded functional language for quantum computation, designed as a unified framework with circuit, algorithm, and circuit-transformation notation. Its Haskell implementation supports higher-order and overloaded operators through advanced type-system features.
- Quipper is an embedded functional programming language intended as a unified general-purpose framework for quantum computation.
- It provides notation for quantum circuits, quantum algorithms, and circuit transformations.
- Seven non-trivial quantum algorithms from the literature were implemented to demonstrate Quipper’s viability.
- Quipper is implemented as an embedded language whose data types, combinators, and library functions reside within Haskell.
- Haskell was chosen because Quipper’s higher-order and overloaded operators use advanced features of Haskell’s type system.
4.2 Quipper’s extended circuit model
Quipper extends the unitary circuit model with explicit qubit lifecycle operations, classical components, and classically controlled quantum gates. Scoped ancillas support resource tracking, while assertive termination relies on programmer-supplied correctness claims.
- Quipper extends unitary circuits with qubit initialization and termination, measurements, classical bits, classical gates, and classically controlled quantum gates.
- Ancilla scopes identify regions where temporary scratch qubits may be used, enabling compilers to track their active computational regions.
- Ancilla allocation from a pool is analogous to classical register allocation and is best deferred to a layout-aware compiler phase.
- The circuit model denotes allocation of a fresh |0⟩ qubit and supports explicit deallocation, including assertive termination when the qubit is known to be |0⟩.
- Scoped ancillas may benefit photonic hardware, where fresh photons are preferable because stored photons have relatively high dissipation rates.
- Assertive termination is a programmer responsibility because the compiler generally cannot verify the algorithm-specific assertion automatically.
- Classical and quantum data can coexist through classical wires, measurements, classical gates, and classically controlled quantum gates.
4.3 The two run-times
Quipper separates compilation, circuit generation, and physical execution into three phases, with the latter two forming distinct run-times. Its type system distinguishes generation-time parameters from execution-time inputs and states.
- Quipper programs have compile time, circuit generation time, and circuit execution time, with generation and execution constituting the two run-times.
- At compile time, Haskell source code and compile-time parameters become executable object code on a classical computer.
- At circuit generation time, executable code and circuit parameters produce a quantum-circuit representation on a classical computer.
- At circuit execution time, a physical quantum computer executes the generated circuit and produces outputs such as measurement results.
- Many algorithms alternate circuit generation and execution as a classical controller sends circuits, receives measurements, and generates subsequent circuits.
- Quipper distinguishes generation-time parameters from execution-time inputs, requiring dedicated programming-language support.
- Bool denotes a generation-time boolean parameter, whereas Bit and Qubit denote execution-time classical and quantum wires.
- For partly input-and-parameter data, the parameter component is called the data’s shape.
4.4 Circuit description language
Quipper supports both gate-level programming and higher-order manipulation of whole circuits, reflecting the predominance of circuit construction and transformation in quantum programming. Its operators cover structured control, ancillas, inversion, decomposition, hierarchical circuits, and multiple execution modes.
- Circuit-level operations: Quantum programming often requires whole-circuit manipulation, including inversion, iteration, ancilla management, gate transformation, optimization, and reversible-circuit generation.The authors estimate that 99 percent of the task involves constructing and manipulating circuits, versus 1 percent running them.
- Circuit-level operations: Quipper combines procedural gate-by-gate programming with higher-order operations for manipulating entire circuits.
- Procedural paradigm: In the procedural paradigm, qubits are held in variables and gates are applied sequentially, with subroutines grouping useful gate-level operations.
- Procedural paradigm: A quantum operation is represented as a function that transforms quantum data within the Haskell Circ monad.
- Block structure: Quipper’s block operators can control an entire gate block and compose subroutines into larger circuits.
- Block structure: The with_ancilla operator supplies a temporary qubit initialized to |0⟩, which code is expected to return to |0⟩ after the block.
- Higher-order operators: Higher-order operators support reversing, iterating, transforming quantum procedures, and converting classical boolean procedures into quantum oracles.
- Higher-order operators: Circuit reversal may be required inside nested subroutines during computation, rather than only after a program finishes.
4.5 Quipper’s extensible quantum data types
Quipper represents quantum data through extensible Haskell type classes, allowing structured quantum values and generic operations beyond individual qubits.
- Type-class abstraction: Quipper uses Haskell type classes to provide an abstract view of quantum data, with definitions inducible over type structure.This abstraction follows the strategy associated with the Quantum IO monad.
- QCData: QCData represents quantum data, including basic Qubit and Bit values, tuples, lists, and library-defined types such as QDInt and FPReal.The representation extends inductively to structured quantum data and supports additional arithmetic and fixed-point real-number types.
- Generic operations: Generic operations can be defined over any QCData instance rather than only over individual qubits.The controlled_not operation applies pairwise controlled-not gates to two quantum data structures.
- QShape: QShape relates quantum inputs to corresponding classical inputs and classical parameter types.Examples include Bool–Qubit–Bit and IntM–QDInt–CInt relationships.
- QShape: Initialization and measurement use QShape-polymorphic functions, allowing them to operate on represented quantum data types.The built-in functions qinit and measure map between classical and quantum representations through Circ.
4.6 Oracles in Quipper
Quipper automates most of the process of turning classical functional programs into reversible quantum oracles, making complex oracle construction practical.
- Automatic generation: Quipper’s circuit lifting automatically performs oracle-construction steps after expressing the oracle as a classical program.The automated stages include translating classical code to circuits and converting those circuits into quantum form; reversibility and uncomputation are also handled by Quipper operators.
- Circuit lifting: The build_circuit mechanism produces a circuit-generating template at compile time, which unpack converts into a quantum circuit function.For a functional parity program, the generated template can be unpacked to obtain a circuit over qubits.
- Reversibility: The classical_to_reversible operator converts a classical circuit generator into a reversible circuit while uncomputing intermediate ancillas.The resulting circuit preserves inputs and outputs while removing scratch-space values.
- Scale: Circuit lifting has been used for large oracles, including a 2.8 million-gate Boolean Formula oracle and a 3273010-gate sin(x) circuit.The sin(x) circuit uses a 32+32 qubit fixed-point argument.
5. The Triangle Finding algorithm in Quipper
The Triangle Finding implementation demonstrates Quipper’s modular circuit construction, boxed subroutines, ancilla management, and ability to generate very large circuits.
- 5.1 Algorithm: The algorithm finds the unique triangle in an oracle-defined graph using a Grover-based quantum walk on its associated Hamming graph.The implementation is parameterized by integers l, n, and r controlling integer length, graph size, and Hamming-tuple size.
- 5.2 Top-level structure: The Triangle Finding implementation is organized into six modules covering definitions, quantum walks, the oracle, execution, simulation, and alternatives.These modules compile into an executable whose command line can select oracles and display circuit components.
- 5.3.1 The subroutine o4: The o4_POW17 oracle subroutine computes a quantum integer’s seventeenth power by repeated squaring followed by multiplication.Its QIntTF arithmetic is taken modulo 2^l −1, and the result is stored in a fresh integer register.
- 5.3.1 The subroutine o4: Quipper boxes reusable subcircuits and with_computed_fun reverses intermediary computations after their results are used.In o4_POW17, the squaring computations are uncomputed after multiplication, while boxed o8_MUL invocations remain visually compact.
- 5.3.1 The subroutine o4: For l = 4, n = 3, r = 2, o4_POW17 uses 71 qubits and 9632 elementary gates, with 4 inputs and 8 outputs.The gate count includes initialization and termination gates, alongside controlled-not gates with one or two controls.
- 5.3.2 The subroutine a6: The a6_QWSH subroutine implements a Hamming-graph walk step by diffusing an index and node, swapping a tuple component, and updating the edge register.Its circuit uses locally initialized ancillas and boxed qRam operations around the node swap.
- 5.4 Aggregate gate counts: The complete Triangle Finding circuit reaches 30189977982990 total gates and 4676 qubits, with gate counting completing in under two minutes on a standard laptop.This count includes repeated quantum-walk steps with inlined oracle invocations.
6. Comparing Quipper and QCL
Compared with QCL on identical Binary Welded Tree implementations, Quipper produces fewer gates, while its automatically generated oracle uses more ancillas but fewer gates than QCL.
- Experimental setup: The comparison uses identical Binary Welded Tree algorithms, with hand-coded oracles in both languages and an additional automatically generated Quipper oracle.All three main circuits use the same parameters.
- Results: QCL produces far more gates than Quipper, including when its hand-coded oracle is compared with Quipper’s automatically generated oracle.The comparison’s Total metric excludes initialization, termination, and measurement gates.
- Results: QCL uses twice as many qubits as the Quipper version with the same oracle.Quipper’s automatically generated-oracle implementation uses more ancillas than QCL but fewer gates.
7. Conclusion
Quipper is presented as a usable and useful scalable functional quantum programming language, demonstrated through seven non-trivial algorithms. Compile-time type checking remains an area for future development because some quantum-data properties are checked only at runtime.
- Quipper was presented as a scalable functional quantum programming language and judged both usable and useful.
- Seven non-trivial quantum algorithms spanning a broad range of quantum computing capabilities were implemented by 11 geographically distributed programmers.
- Approximately 55 man months of work produced representations usable for resource estimation with realistic problem sizes.
- Without a linear type system, properties such as non-duplication of quantum data must be checked at runtime.Improving compile-time type checking is identified as future work.