Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs
arXiv:2408.10054 · doi:10.1145/3729283
Abstract
Quantum recursive programming has been recently introduced for describing sophisticated and complicated quantum algorithms in a compact and elegant way. However, implementation of quantum recursion involves intricate interplay between quantum control flow and recursive procedure calls. In this paper, we aim at resolving this fundamental challenge and develop a series of techniques to efficiently implement quantum recursive programs. Our main contributions include: 1. We propose a notion of quantum register machine, the first quantum architecture (including an instruction set) that provides instruction-level support for quantum control flow and recursive procedure calls at the same time. 2. Based on quantum register machine, we describe the first comprehensive implementation process of quantum recursive programs, including the compilation, the partial evaluation of quantum control flow, and the execution on the quantum register machine. 3. As a bonus, our efficient implementation of quantum recursive programs also offers automatic parallelisation of quantum algorithms. For implementing certain quantum algorithmic subroutine, like the widely used quantum multiplexor, we can even obtain exponential parallel speed-up (over the straightforward implementation) from this automatic parallelisation. This demonstrates that quantum recursive programming can be win-win for both modularity of programs and efficiency of their implementation.
arXiv comment63 pages, 25 figures. Extended version of PLDI 2025 publication
References in corpus (34)
- Quantum random access memory
- Simulating Hamiltonian dynamics with a truncated Taylor series
- Synthesis of Quantum Logic Circuits
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity
- Hamiltonian simulation with nearly optimal dependence on all parameters
- Architectures for a quantum random access memory
- Low Depth Quantum Simulation of Electronic Structure
- A divide-and-conquer algorithm for quantum state preparation
- Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications
- Hardware-efficient quantum random access memory with hybrid quantum acoustic systems
- Exponentially more precise quantum simulation of fermions I: Quantum chemistry in second quantization
- Parallelizing Quantum Circuits
- A functional quantum programming language
- A Verified Optimizer for Quantum Circuits
- Quantum Circuits with Unbounded Fan-out
- Trading T gates for dirty qubits in state preparation and unitary synthesis
- Resilience of quantum random access memory to generic noise
- Verified compilation of space-efficient reversible circuits
- Quantum Nondemolition Monitoring of Universal Quantum Computers
- ReQWIRE: Reasoning about Reversible Quantum Circuits
- Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits
- Remarks on Universal Quantum Computer
- On Halting Process of Quantum Turing Machine
- Tower: Data Structures in Quantum Superposition
- Quantum Alternation: Prospects and Problems
- Circuit complexity of quantum access models for encoding classical data
- Parallel Quantum Algorithm for Hamiltonian Simulation
- A Case for Synthesis of Recursive Quantum Unitary Programs
- The T-Complexity Costs of Error Correction for Control Flow in Quantum Computation
- Quantum Control Machine: The Limits of Control Flow in Quantum Programming
- Reqomp: Space-constrained Uncomputation for Quantum Circuits
- Quantum Random Access Stored-Program Machines
- Fat-Tree QRAM: A High-Bandwidth Shared Quantum Random Access Memory for Parallel Queries