A Practical Quantum Instruction Set Architecture

Robert S. Smith; Michael J. Curtis; William J. Zeng

Source-linked AI summary

A Practical Quantum Instruction Set Architecture

Robert S. Smith, Michael J. Curtis, William J. Zeng

arXiv:1608.03355v2Aug 11, 2016quant-phcs.ETcs.PL

TL;DR

The paper addresses the need for practical programming and compilation frameworks for hybrid classical/quantum algorithms. It introduces the QAM and Quil as a portable instruction-set architecture, then presents implementations, tools, and algorithm examples, including a simulator demonstrated to simulate 36 qubits.

Problem
Hybrid algorithms require new programming architectures, compilation frameworks, and emulation support beyond the quantum Turing machine model.
Method
The paper defines the QAM abstract machine, the Quil instruction language, and associated tools for program analysis, compilation, construction, and execution.
Results
The Rigetti QVM provides a programmable simulator and noisy-quantum-computer emulator, and it has been demonstrated to simulate 36 qubits.
Takeaways & Limitations
The QAM and Quil provide a practical notation and toolkit for describing, analyzing, compiling, and executing hybrid quantum programs.

Abstract

from arXiv · show

We introduce an abstract machine architecture for classical/quantum computations---including compilation---along with a quantum instruction language called Quil for explicitly writing these computations. With this formalism, we discuss concrete implementations of the machine and non-trivial algorithms targeting them. The introduction of this machine dovetails with ongoing development of quantum computing technology, and makes possible portable descriptions of recent classical/quantum algorithms.

III-N The Standard Gates . . . . . . . . . .

The paper motivates a practical quantum instruction-set architecture for hybrid classical/quantum computation and defines the mathematical state-space foundations underlying the QAM. It connects this framework to compilation, feedback, and executable implementations.

I. Introduction: Hybrid classical/quantum algorithms require coordinated classical and quantum computers, with classical information returned through an efficiently implementable memory model.The feedback loop supports cooperative execution between the two computing systems.
I. Introduction: The paper introduces the QAM as an abstract machine for hybrid computation, together with Quil, a language suitable for analysis, compilation, and execution.The QAM state includes quantum state, classical memory, gate sets, program instructions, and an instruction pointer.
II. The Quantum Abstract Machine: The QAM can be implemented either classically as a Quantum Virtual Machine or on quantum hardware as a Quantum Processing Unit.This provides a common abstract model across simulation and hardware execution.
A. Qubit Semantics: Tensor-product basis elements use a lexicographic indexing convention that corresponds to binary indices when written as bit strings.The paper introduces bit-string notation for this useful indexing property but does not use it throughout.
A. Qubit Semantics: A system of Nq qubits has a tensor-product Hilbert space whose dimension is 2^Nq, so its state can be represented by a complex vector of that length.The qubits begin in the all-zero state, while classical memory is initialized to zero.

B. Quantum Gate Semantics

Quantum gate semantics describe how local one- and two-qubit operators become operators on the full QAM Hilbert space. The construction uses tensoring with identities for adjacent qubits and permutations for nonadjacent qubits.

B. Quantum Gate Semantics: Quantum gates are generally 2^Nq × 2^Nq unitary operators, although Quil commonly specifies one- or two-qubit gates that must be lifted before application.Lifting embeds a local operator into the full Hilbert space.
B. Quantum Gate Semantics: A one-qubit gate acting on Qk is lifted by tensor-multiplying it with identity maps in the remaining qubit positions.The operator occupies the position determined by k under the paper’s indexing convention.
B. Quantum Gate Semantics: A two-qubit gate on adjacent Hilbert spaces is lifted by inserting the local operator among identity factors.The construction places the operator at the appropriate position in the tensor product.
B. Quantum Gate Semantics: For nonadjacent qubits, the method permutes tensor factors to make them adjacent, applies the gate, and reverses the permutation.Adjacent transpositions and SWAP-based permutation operators provide the required bookkeeping.
B. Quantum Gate Semantics: The full lifting construction generalizes to gates acting on arbitrary numbers of qubits and defines all liftings over qubit permutations.The set L(U) collects the lifted forms associated with those permutations.

C. Measurement Semantics

Measurement in the QAM is nondeterministic and projects the quantum state through selected measurement operators. The operator is chosen probabilistically, after which the state undergoes an irreversible collapse.

C. Measurement Semantics: Measurement is a nondeterministic, surjective-only operation with two outcomes for a single qubit.The outcomes correspond to applying lifted measurement operators up to a scalar factor.
C. Measurement Semantics: The measurement operators can be interpreted as projections onto basis elements of the relevant Hilbert space.The paper also describes a more general finite-dimensional set of measurement operators.
C. Measurement Semantics: The probability of selecting a measurement operator µ is P(µ) := ⟨Ψ|˜µ†˜µ|Ψ⟩.The QAM lifts the selected operator before applying it to the quantum state.
C. Measurement Semantics: After an operator is selected, the quantum state transforms according to the measurement operation and undergoes irreversible wavefunction collapse.The collapse follows the operator-selection step in the QAM semantics.
C. Measurement Semantics: More generally, Hermitian observables yield eigenvalues as measurement outcomes and collapse the state to corresponding eigenvectors.This broader quantum-mechanical interpretation is noted beyond the basic QAM description.

III. Quil: a Quantum Instruction Language

Quil is an instruction-based, assembly-like language that represents quantum computations with classical feedback and control. It defines operations over qubits and classical memory, including measurement, synchronization, branching, modular definitions, and numerical parameter interpretation.

III. Quil: a Quantum Instruction Language: Quil represents quantum computations with classical feedback and control in a line-based, assembly-like instruction format.It can be written directly, used as an intermediate format, or serve as a compilation target.
III. Quil: a Quantum Instruction Language: Quil supports arbitrary gates, parameterized gate and circuit definitions, circuit expansion, measurement, synchronization, branching, and modular file inclusion.These capabilities define the principal operations available in the language.
III. Quil: a Quantum Instruction Language: Quil code effects transitions of the Quantum Abstract Machine as a state machine.The language’s instructions are specified against the QAM state and conventions.
A. Classical Addresses and Qubits: The core operands are qubits, classical bits identified by addresses, and classical memory segments.Qubits and classical memory are the atomic objects on which Quil operations act.
A. Classical Addresses and Qubits: Qubits use integer indices, while classical addresses use bracketed integers such as.A classical memory segment is written as a bracketed inclusive range, such as [0-63].
A. Classical Addresses and Qubits: A memory segment [0-63] represents bits C[63]C[62] ... C[1]C[0] in MSB-to-LSB order.Segments are contiguous inclusive address ranges and can represent concatenated bits.
B. Numerical Interpretation of Classical Memory Segments: Classical memory segments can supply numerical values for controlling parametric gates.A 64-bit segment denotes an IEEE-754 double, while a 128-bit segment denotes a double-precision complex number a + ib formed from two 64-bit halves.

C. Static and Parametric Gates

Quil distinguishes static gates from parametric gates and provides syntax for invoking, defining, and composing them. Gate and circuit definitions support matrix expressions, formal parameters, substitution, and reusable macro-like expansion, while some malformed or dynamic cases have undefined or costly semantics.

C. Static and Parametric Gates: The QAM distinguishes static gates, which are operators in U(2^Nq), from parametric gates, which are functions C^n → U(2^Nq).Parametric gates use complex numbers as parameters, and Quil abstracts away the lifting of gates to the QAM Hilbert space.
C. Static and Parametric Gates: Quil defines each gate separately from its invocation, using a symbolic name followed by a fixed number of qubit arguments.Invoking a gate whose required lifting is absent from G or G′ is undefined.
C. Static and Parametric Gates: Static and parametric gate invocations use qubit arguments, with parametric calls additionally supplying numerical parameters.The examples show H 0 CNOT 0 1 and PNAME(0.9009688679-0.4338837391i) 1 0 4.
C. Static and Parametric Gates: A constant parameter can be treated either as a resulting static gate in G or as a parametric gate instance in G′.Dynamic parameters may instead be supplied from a classical memory segment.
D. Gate Definitions: Static gates are defined by matrix entries written with scientific notation or constant arithmetic expressions, and declared with DEFGATE.Supported expressions include arithmetic, pi, i, sin, cos, sqrt, exp, and cis.
D. Gate Definitions: Matrices that are not unitary, up to noise or precision, have undefined execution semantics.Software processing Quil is encouraged to warn or error on such matrices.
D. Gate Definitions: Parametric gate definitions add formal parameters prefixed with %, as in the Rx definition using %theta.Formal parameters appear in parentheses after the gate name and can occur in matrix expressions.
H. Circuit Definitions: DEFCIRCUIT defines reusable parameterized instruction sequences with arguments substitutable by classical addresses or qubits.Circuits expand repeatedly but function mainly as macros for debugging and readability, not general circuit specifications.

F. Measurement

Quil uses measurement to alter quantum state or record results in classical memory, and uses program-control instructions to branch and jump through labeled instruction sequences. Conditional jumps provide classical feedback based on stored bits.

F. Measurement: Measurement is an essential source of quantum-program side effects and has measurement-for-effect and measurement-for-record forms.The former changes the quantum state, while the latter records a result in classical memory.
F. Measurement: Measurement-for-record takes a qubit and classical memory address, depositing the measured bit at that address.Measuring Q7 into address 8 illustrates the two-argument MEASURE form.
F. Measurement: Measuring qubits 0 and 1 into [0] and produces a random number from 0 through 3 represented in binary by memory [0-1].The example uses two MEASURE instructions to construct the binary result.
G. Program Control: The program counter κ advances after ordinary instructions and changes through jumps or termination instructions.HALT assigns κ ← |P|, and the final instruction implicitly terminates execution.
G. Program Control: Labels introduced with LABEL name instruction locations, while JUMP sets κ to the index of a specified target.Labels use names prefixed by @.
G. Program Control: JUMP-WHEN and JUMP-UNLESS branch on whether a classical-memory bit is 1 or 0, otherwise advancing to κ + 1.The paper identifies this conditional feedback as a critical differentiating element of Quil.
G. Program Control: Conditional branching in Quil translates an if-statement into a conditional jump, an unconditional jump, and labeled targets.The example branches on the bit stored at address x.
G. Program Control: Circuit-local labels are unique to each circuit: programs can jump out to global labels but cannot jump into a circuit.The examples mark jumps into circuit-local labels as invalid.

H. Zeroing the Quantum State

Quil resets the entire quantum state directly but clears individual qubits through measurement, classical control, and conditional correction. WAIT synchronizes classical and quantum computation, while classical instructions and file inclusion support control and modularity.

H. Zeroing the Quantum State: RESET sets the QAM quantum state to the zero state.Quil does not provide a direct instruction for clearing only one qubit.
H. Zeroing the Quantum State: A single qubit can be cleared by measuring it into scratch space, conditionally applying X, and terminating through a local label.The CLEAR circuit uses MEASURE, JUMP-UNLESS, X, and LABEL.
I. Synchronization: WAIT suspends program execution until classical computation and corresponding classical-state modification satisfy an implementation-defined condition.WAIT takes no arguments and signals synchronization between classical and quantum computation.
J. Classical Instructions: Quil delegates most classical computation to a classical computer and uses synchronization to mediate data exchange with the quantum processor.Only a small set of classical-state instructions is included for convenience and control flow.
J. Classical Instructions: Unary classical instructions FALSE, TRUE, and NOT modify one addressed bit, while binary instructions operate on two addressed bits.The binary-instruction section introduces operations over paired classical addresses.
J. Classical Instructions: The binary instructions include AND, OR, MOVE, and EXCHANGE, which combine, copy, or swap classical bits.Their effects are defined through updates to C[a] and C[b].
J. Classical Instructions: Quil can implement XOR as a circuit using classical moves, OR, NOT, and short-circuit control, with r distinct from a and b.The construction uses a conditional jump to skip the second branch when appropriate.
K. No-Operation: NOP leaves the QAM state unchanged apart from incrementing the program counter and can distinguish noiseless no-ops from noisy identity gates during emulation.It can also force a break in instruction parallelization.

M. Pragma Support

PRAGMA directives let Quil programs carry processing information without changing QAM execution semantics, including barriers and gate timings. The section also presents QFT construction through recursive Hadamard, controlled-phase, and SWAP operations.

M. Pragma Support: PRAGMA directives attach identifiers and optional strings to Quil programs without changing their execution semantics.The syntax requires one or more identifiers and permits an optional string.
M. Pragma Support: A parallelization-barrier pragma can prevent implementations from parallelizing across otherwise commuting instructions.The example places a barrier between X 0 and X 1, while QAM semantics remain unchanged.
M. Pragma Support: Gate-time pragmas allow programs to specify physical execution durations, such as 50 ns for H and 150 ns for CNOT.These durations can affect instruction scheduling on superconducting architectures.
Quantum Fourier Transform: QFT implementation requires reversing basis-element order, which is realized with exactly ⌊Nq/2⌋ SWAP gates.The routine pairs qubit i with qubit Nq - i - 1.
Quantum Fourier Transform: The QFT factorization acts on each target qubit with controlled-phase gates, reducing to a Hadamard in the one-qubit case.The recursive QFT' routine uses a Hadamard as its base case and controlled-phase gates followed by a Hadamard otherwise.

B. Variational Quantum Eigensolver

VQE combines a parameterized quantum state-preparation and measurement routine with a classical optimization loop. The paper contrasts static code regeneration with a dynamic implementation that encapsulates the quantum program but is harder to implement in hardware.

B. Variational Quantum Eigensolver: VQE prepares a parameterized quantum state, measures its Hamiltonian expectation value, and uses classical optimization to vary parameters until convergence.The quantum and classical portions form an iterative hybrid computation.
1) Static Implementation: A static VQE implementation generates and loads a new Quil program for every parameter setting.The example inserts a numerical parameter directly into an RZ instruction before measurement.
1) Static Implementation: The static approach avoids coherence-time problems but adds a time penalty to each classical-optimizer iteration.Its implementation is described using pyQuil and the Rigetti QVM.
2) Dynamic Implementation: A dynamic VQE implementation defines a parameterized circuit and communicates parameters, convergence status, and measurements through classical memory.The circuit uses PREP_STATE, MEASURE, WAIT, and JUMP-UNLESS to repeat until convergence.
2) Dynamic Implementation: The dynamic program encapsulates the quantum computation and eliminates the need to reload Quil code for each varied parameter.This is presented as its principal advantage over static regeneration.
2) Dynamic Implementation: Dynamic VQE is harder to implement in hardware because runtime gate choices reduce opportunities for pre-execution program analysis and optimization.Current architectures have limited native gate sets and limited high-speed dynamic tune-up of new gates or approximations.
Applications and Tools: Forest organizes quantum software into applications and tools, Quil, compiler, and execution-unit layers.Execution units include QPUs, QVMs, and hardware emulators, while Quil serves as an intermediate representation.

B. Applications and Tools

Quil supports programmatic construction, static analysis, compilation, routing, and symbolic control-flow analysis. These capabilities connect a human-readable instruction language to execution on machines with restricted gate sets and qubit topologies.

B. Applications and Tools: pyQuil treats Quil programs as first-class objects and supports construction of non-trivial algorithms such as VQE with scientific libraries.Quil itself remains human readable and writable, while programmatic manipulation adds expressive power.
B. Applications and Tools: Quil can be parsed and converted into structured JSON independently of a physical or virtual execution machine.The analyzer marks gates as unresolved applications when they are not defined in the Quil file.
D. Compilation: Compilation converts gate sequences into approximately equivalent sequences executable on a target architecture through gate approximation and routing.Approximation reduces gates to a native set, while routing arranges them for neighboring physical qubits.
D. Compilation: Quil programs can be decomposed into control-flow graphs whose nodes are basic blocks of straight-line instructions and whose arrows represent control transfers.Figure 3 depicts such a graph with jump instructions elided.
D. Compilation: Routing on a linear three-qubit topology replaces nonadjacent operations with SWAP sequences and corresponding adjacent gates.The transformation gives the illusion of a fully connected topology while respecting the hardware connectivity constraint.
D. Compilation: QAM transformations also support G-preserving algebraic simplifications analogous to compiler peephole optimization.These transformations operate on program gate sets while preserving computational behavior.

E. Instruction Parallelism

Quil remains serial in written form but supports parallel execution within suitable basic blocks, while the Rigetti QVM provides local, remote, and noisy-emulation execution paths. Together, these mechanisms support practical development and execution of quantum programs.

E. Instruction Parallelism: Quil instruction sequences can execute in parallel when operations commute or measurements use non-overlapping classical memory addresses.The language is linear and serial as written but may be interpreted as an instruction-parallel program.
E. Instruction Parallelism: Parallelization generally cannot cross jumps, resets, waits, measurements, or dynamic gate applications with overlapping address ranges.NOP can be used to force a parallelization break.
E. Instruction Parallelism: Control-flow graphs permit parallelization independently within each basic block, producing a parallelization schedule.Figure 4 illustrates this scheduling within a CFG, marking parallel instruction sequences with curly braces.
F. Rigetti Quantum Virtual Machine: The Rigetti QVM is an ANSI Common Lisp simulator for the QAM and an emulator for noisy quantum computers.It supports direct Quil-file execution through local POSIX-style shared memory and remote execution through HTTP requests.
F. Rigetti Quantum Virtual Machine: Local QVM execution supports high-speed testing, direct quantum-state inspection, debugging, and tunable-noise hardware emulation.These capabilities target small-to-medium-sized classical/quantum algorithm instances.
F. Rigetti Quantum Virtual Machine: Remote QVM execution provides distributed cloud access through HTTP libraries available in modern programming languages.pyQuil can send first-class Quil program objects to local or secured remote QVM instances through the Forest API.
F. Rigetti Quantum Virtual Machine: The Rigetti QVM has optimized vectorized and parallelized numerics and has been demonstrated to simulate 36 qubits.The passage states that it has no theoretical limit for the number of qubits it can simulate.
VI. Conclusion: The paper concludes that its abstract machine, Quil notation, and toolkit support reasoning about, analyzing, compiling, and executing quantum programs.These components form the practical software stack described by the paper.

Appendix

Quantum programming languages and representations span embedded, high-level, and low-level forms, alongside larger tool chains. Quil is positioned as a low-level quantum intermediate representation that includes classical control and can serve as a compilation target.

Related work: Quantum programming work includes embedded domain-specific languages, high-level quantum programming languages, and low-level quantum intermediate representations.
Embedded domain-specific languages: EDSLs such as Quipper and LIQUi|⟩ represent quantum programs as host-language data structures that can be processed and compiled.Their programs are not directly executable on quantum hardware because they require the host language’s runtime.
High-level quantum programming languages: High-level languages provide classical and quantum data types with control-flow constructs, exemplified by QCL’s int and qureg types and measurement operations.QCL demonstrates Hadamard initialization of eight qubits and measurement of four qubits into an integer variable.
High-level quantum programming languages: QCL semantics and interpretation are described in detail, but its prior work does not present a compilation or execution strategy on quantum hardware.QCL, like other high-level quantum languages, can be compiled into a lower-level instruction set such as Quil.
Low-level quantum intermediate representations: QASM describes executable quantum circuits but lacks classical control, whereas Quil is a low-level quantum IR with classical control.Low-level IRs generally support further processing, analysis, optimization, or compilation, as illustrated by classical IRs such as LLVM IR.