# Qwerty: A Basis-Oriented Quantum Programming Language

Austin J. Adams  0000-0002-3179-8735 Georgia TechAtlantaUSA ,  Sharjeel Khan
0000-0002-4563-4619 Georgia TechAtlantaUSA ,  Jeffrey S. Young
0000-0001-9841-4057 Georgia TechAtlantaUSA and  Thomas M. Conte
0000-0001-7037-2377 Georgia TechAtlantaUSA

(18 April 2024)

###### Abstract.

Quantum computers have evolved from the theoretical realm into a race to
large-scale implementations. This is due to the promise of revolutionary
speedups, where achieving such speedup requires designing an algorithm that
harnesses the structure of a problem using quantum mechanics. Yet many quantum
programming languages today require programmers to reason at a low level of
quantum gate circuitry. This presents a significant barrier to entry for
programmers who have not yet built up an intuition about quantum gate
semantics, and it can prove to be tedious even for those who have. In this
paper, we present Qwerty, a new quantum programming language that allows
programmers to manipulate qubits more expressively than gates, relegating the
tedious task of gate selection to the compiler. Due to its novel basis type
and easy interoperability with Python, Qwerty is a powerful framework for
high-level quantum–classical computation.

Website: qwerty.cc.gatech.edu. Contact<EMAIL_ADDRESS>
##  1\. Introduction

Quantum computers have evolved from the theoretical realm into an active and
highly competitive commercial race to large-scale implementations. This is due
to the promise of revolutionary speedups for important problems such as
unstructured search and factoring large integers (Grover, 1996; Shor, 1999;
Nielsen and Chuang, 2010). Achieving such speedup requires designing an
algorithm that harnesses the structure of a problem using quantum mechanics
(Shor, 2003; Aaronson, 2022). Yet even if a programmer understands how a
quantum algorithm operates, realizing the algorithm using existing quantum
programming languages requires a mastery of quantum gate engineering. This
significant, abrupt gap between algorithms and low-level quantum gates
suggests a need for a quantum programming language beyond gates.

Table 1. Comparison with Prior Work on Advancing Quantum Programming Name |  Computational construct | Key feature(s)
---|---|---
QCL (Ömer, 2000) | Gates | First quantum programming language
Scaffold (Abhari et al., 2012; Litteken et al., 2020) | Gates | Integration with C++, oracle synthesis
Quipper (Green et al., 2013) | Gates | Functional circuit construction
Qiskit (Qiskit contributors, 2023) | Gates | Convenient Python integration, rich tooling
Q# (Svore et al., 2018; Lubinski et al., 2022) | Gates | Standard library and functional programming
QCOR (Mintz et al., 2020; Mccaskey et al., 2021) | Gates | C++ integration, physics features
OpenQASM 3 (Cross et al., 2022) | Gates | Adds structured control flow to circuits
Qwire (Paykin et al., 2017) | Gates | Linear qubit types
Silq (Bichsel et al., 2020), Qiskit++ (Paradis et al., 2021) | Gates | Simplifies managing uncomputation efficiently
Qunity (Voichick et al., 2023) | Gates | Unifies quantum and classical programming
Twist (Yuan et al., 2022) | Gates | Prevents accidental entanglement bugs
Tower (Yuan and Carbin, 2022) | Linked lists | Quantum data structures
quAPL (Núñez-Corrales et al., 2023) | Gates | Introduces a quantum array language
Quantum$\Pi$ (Carette et al., 2023) | Gates | Defines a quantum PL using classical PLs
Oqasm (Li et al., 2022) | Gates | Basis-aware circuit-level programming
Oqimp (Li et al., 2022) | Classical code | Verified synthesis of black-box oracles
Neko (Pinto, 2023) | MapReduce | Programs have map-filter-reduce structure
Aleph (Paz, 2023) | Universes | User-friendly amplitude amplification
Qwerty (this work) |  Basis Translations | Gate-free programming, Python integration

Table 1 summarizes the computational constructs and key features of existing
quantum programming languages. The “computational construct” column is meant
as the main tool programmers realistically employ to express quantum
operations. For instance, the theoretical work Quantum$\Pi$ explores a novel
quantum programming language design. Ultimately though, after defining gates
in terms of these new features, the paper’s example programs are presented in
terms of gates (Carette et al., 2023, §9). A few prior languages allow quantum
programming without gates: Tower (Yuan and Carbin, 2022), Oqimp (Li et al.,
2022), Neko (Pinto, 2023), and Aleph (Paz, 2023). However, these languages are
not suitable for efficient general-purpose quantum programming. Tower focuses
only on data structures; Oqimp is designed specifically for synthesizing
oracles (Quipper (Green et al., 2013) contains similar functionality); Neko
requires that the algorithm is compatible with a map-filter-reduce structure;
and Aleph synthesizes only amplitude amplification and thus cannot achieve
exponential speedup for factoring, for instance.

In this paper, we present Qwerty, a new quantum programming language. Thanks
to Qwerty’s novel basis type and its ability to embed classical computation in
quantum code, Qwerty allows programmers to implement algorithms with
prospective quantum advantage without low-level gate engineering. Because
Qwerty is embedded as a Python DSL, interoperability between Python and Qwerty
is easy, making Qwerty a robust framework for mixed quantum–classical
computation.

Qwerty is introduced through examples, first via the Bernstein–Vazirani
algorithm (Section 3.1) and then many prominent quantum algorithms (Section
4). An introduction to quantum notation is provided for the non-expert
(Section 2). Appendix A presents the soundness of the semantics and type
system of Qwerty.

##  2\. Introduction to Quantum Notation

(This section introduces quantum computing notation. Readers who are familiar
already can safely skip to the next section of the paper.)

The state of a qubit is a unit vector in a 2D complex vector space with an
inner product — a Hilbert space — which we will write as $\mathcal{H}_{2}$. In
bra–ket (or Dirac) notation, $\left|\psi\right\rangle$ denotes a vector in
$\mathcal{H}_{2}$. The inner product of $\left|\phi\right\rangle$ and
$\left|\psi\right\rangle$ is written as
$\left\langle\phi\middle|\psi\right\rangle$. Given two qubits with states
$\left|\psi\right\rangle$ and $\left|\phi\right\rangle$, the state of the two-
qubit system is written with the tensor product $\otimes$ as
$\left|\psi\right\rangle\otimes\left|\phi\right\rangle$; this product is a
unit vector in a four-dimensional Hilbert space
$\mathcal{H}_{2}{}\otimes\mathcal{H}_{2}{}$. (It is common to write
$\left|\psi\right\rangle\left|\phi\right\rangle$ as shorthand for
$\left|\psi\right\rangle\otimes\left|\phi\right\rangle$.) This pattern
continues, with every additional qubit doubling the dimension of the state
space, i.e., doubling the number of complex numbers (amplitudes) needed to
describe a state.

The vectors $\left|0\right\rangle$ and $\left|1\right\rangle$ represent the
standard basis for a one-qubit (2D) space. For a two-qubit (4D) space, the
vectors $\left|00\right\rangle$, $\left|01\right\rangle$,
$\left|10\right\rangle$, and $\left|11\right\rangle$ are the standard basis.
In general, the $2^{n}$ standard basis vectors for an $n$-qubit state are
labeled with $n$-bit bitstrings. Typical measurement projects onto one of
these standard basis states, with the bits labeling the basis state being the
measurement outcome, and the likelihood being proportional to the norm of the
projection. (Note that in fact, measurement can be performed in any basis,
although this may not be convenient in hardware.) For example, the state
$\sqrt{9/10}\left|00\right\rangle+\sqrt{1/10}\left|11\right\rangle$ is most
likely to produce the measurement $00$ when measuring in the standard basis,
since the projection onto $\left|00\right\rangle$ has a larger norm than the
projection onto $\left|11\right\rangle$.

Qubit state must evolve reversibly, which can be expressed as requiring it to
evolve by a $2^{n}{\times}2^{n}$ unitary operator $U$, like
$\left|\psi^{\prime}\right\rangle=U\left|\psi\right\rangle$. The unitary
condition is that $U$ is invertible and
$||U\left|\psi\right\rangle||=||\left|\psi\right\rangle||$ (Axler, 2023),
i.e., that $U^{-1}$ exists and that $U$ always preserves the norm of any input
$\left|\psi\right\rangle$. By the spectral decomposition, any unitary can be
expressed as a diagonal matrix
$U=\sum_{\lambda}\lambda\left|\lambda\right\rangle\left\langle\lambda\right|$
(Nielsen and Chuang, 2010). For example, the Pauli X matrix
$\sigma_{x}=\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}$ can be diagonalized as
$\sigma_{x}=\begin{bmatrix}1&0\\\ 0&-1\end{bmatrix}$ if the rows and columns
are written in terms of the basis $\left|+\right\rangle,\left|-\right\rangle$
rather than the standard $\left|0\right\rangle,\left|1\right\rangle$ basis.
(The vectors
$\left|+\right\rangle\triangleq\frac{1}{\sqrt{2}}\left(\left|0\right\rangle+\left|1\right\rangle\right)$
and
$\left|-\right\rangle\triangleq\frac{1}{\sqrt{2}}\left(\left|0\right\rangle-\left|1\right\rangle\right)$.
Both are eigenvectors of $\sigma_{x}$.)

For a more thorough introduction to quantum computing and its notation, we
direct readers to Chapters 1 and 2, respectively, of Nielsen and Chuang
(Nielsen and Chuang, 2010).

##  3\. Introduction to Qwerty

###  3.1. Motivating Example: Bernstein–Vazirani

Figure 1. A comparison between Q# and Qwerty implementations of the
Bernstein–Vazirani algorithm (Paz et al., 2023), which finds a secret string
$s$ with only one invocation of black-box implementation of a classical
function $f(x)=x\cdot s$.

To introduce Qwerty, we begin with an example using the well-known
Bernstein–Vazirani algorithm (Bernstein and Vazirani, 1993; Fallek et al.,
2016). Assume there is a secret $n$-bit bitstring $s$ and a “black-box”
function that performs $f(x)=x_{1}s_{1}\oplus x_{2}s_{2}\oplus\cdots\oplus
x_{n}s_{n}$. (Here, $\oplus$ denotes XOR, and $x_{i}s_{i}$ denotes ANDing
$x_{i}$ with $s_{i}$.) The Bernstein–Vazirani algorithm returns $s$ using only
a single invocation of $f(x)$ — a classical solution would need $n$
invocations ($f(100\cdots 0)$ to get $s_{1}$, $f(010\cdots 0)$ to get $s_{2}$,
etc.).

The steps in the Bernstein–Vazirani algorithm are shown mathematically in the
center column of Fig. 1. Each of the four steps corresponds to a key primitive
(or feature) of Qwerty: (1) qubit state preparation (i.e., initialization),
(2) application of the reversible version of $f(x)$, (3) basis translation,
and (4) measurement. The first step prepares the initial state
$\left|{+}{+}\cdots{+}\right\rangle$. Then, when $f(x)$ is applied in the next
step, each $\left|+\right\rangle$ in this state is changed to a
$\left|-\right\rangle$ state if the corresponding bit of $s$ is $1$. The next
step is the most pivotal step, where all qubits undergo the transformation
$\alpha\left|+\right\rangle+\beta\left|-\right\rangle\rightarrow\alpha\left|0\right\rangle+\beta\left|1\right\rangle$.
In Qwerty, this transformation is called a basis translation from the basis
$\left|+\right\rangle,\left|-\right\rangle$ to the basis
$\left|0\right\rangle,\left|1\right\rangle$. We call this a translation
because when representing the input state as a linear combination of basis
vectors, it translates the basis vectors element-wise into a different basis
without touching the coefficients (i.e., the amplitudes)111Traditionally in
quantum computing, this operation might be called a “change of basis”, but we
have found this term is too easily confused with the linear algebra procedure
(Axler, 2023) that changes only the representation of a vector, not its
value..

The right-hand column of Fig. 1 shows Bernstein–Vazirani written in Qwerty.
Contrast this with the left-hand column of Fig. 1, which shows the same
algorithm written in Q# (Paz et al., 2023), a prominent quantum programming
language. Not only is Qwerty more concise, but it is also more expressive. For
example, the highlighted Q# lines in Fig. 1 perform both routine state
preparation and also the most crucial part of the algorithm, basis
translation. By contrast, Fig. 1 shows that the Qwerty code has explicit
syntax for both steps: preparing $\left|+\right\rangle^{\otimes n}$ (written
as ’+’[N]) and translating from the $n$-qubit plus/minus basis to the
$n$-qubit standard basis (written as pm[N] >> std[N]). Compared to the mere H
used in the Q# code, which represents a low-level Hadamard gate, these Qwerty
constructs allow programmers to better express intent.

Quantum algorithms aimed at classical problems typically invoke classical
functions on qubits, so language support for expressing this classical logic
intuitively is just as important as convenient expression of quantum logic.
The bottom of Fig. 1 compares expressions of such classical logic in Q# versus
Qwerty. Even though the Bernstein–Vazirani black-box function $f(x)$ can be
easily expressed with well-known classical logic gates, Q# requires either
programming in quantum gates (bottom left of Fig. 1) or calling library
functions that apply quantum gates. In Qwerty, on the other hand, programmers
can express classical functions directly as classical logic, as shown in the
bottom right of Fig. 1. Such classical functions can be invoked directly from
Python and execute in the Python interpreter, or they can be instantiated
inside quantum code (top right of Fig. 1) and lowered to quantum gates by the
compiler. Combined with the aforementioned mechanisms for state preparation
and basis translation, this functionality allows programmers to implement
well-known quantum algorithms such as Grover’s or Shor’s efficiently without
writing a single quantum gate.

###  3.2. Overview of Qwerty

In this section, we present the key Qwerty features that enable more
expressive quantum programming.

####  3.2.1. The qubit type

The qubit type in Qwerty is linear (Selinger and Valiron, 2006; Paykin et al.,
2017), meaning that every qubit must be used exactly once. This prevents
attempting to duplicate qubit states, which violates the no-cloning theorem
(Nielsen and Chuang, 2010), or accidentally discarding a qubit entangled with
other qubits, causing unexpected behavior (Yuan et al., 2022).

⬇ use q = Qubit(); H(q);

(a) Q#: Preparing $|+\rangle$

⬇ ’+’

(b) Qwerty: Preparing $|+\rangle$

⬇ use q = Qubit[3]; X(q[0]); X(q[2]);

(c) Q#: Preparing $|101\rangle$

⬇ ’101’

(d) Qwerty: Preparing $|101\rangle$

Figure 2. Side-by-side comparison of state preparation in traditional gate-
based languages versus in Qwerty.

##### Qubit literals

Programmers can introduce qubits using qubit literals, which efficiently
prepare a subset of qubit states. For example, ’-’ prepares the state
$|-\rangle$, ’110’ prepares the state $\left|110\right\rangle$, and so on.
Fig. 2 demonstrates how Qwerty qubit literals are more succinct and expressive
than equivalent code in gate-oriented languages.

##### Tensor product

In general, one can (loosely) view the tensor product as concatenating vectors
or vector spaces (Nielsen and Chuang, 2010; Axler, 2023). Thus, given that a
string-like syntax is used for qubit literals, the typical string
concatenation operator + is a natural fit for the tensor product. For
instance, ’1’ + ’0’ + ’1’ is equivalent to ’101’. Repeated tensor product is
accomplished with ’0’[N], which is equivalent to
${{{\underbrace{\text{\leavevmode\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@language{\@listingGroup{ltx_lst_string}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\textquoteright
0\textquoteright}}+{\@listingGroup{ltx_lst_string}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\textquoteright
0\textquoteright}}+}}}}\cdots\text{\leavevmode\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@language+{\@listingGroup{ltx_lst_string}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\textquoteright
0\textquoteright}}}}}}}_{{\text{\leavevmode\lstinline{{\lst@@@set@language\lst@@@set@numbers\lst@@@set@frame\lst@@@set@rulecolor\lst@@@set@language{\@listingGroup{ltx_lst_identifier}{N}}}}}}}}$.

####  3.2.2. The basis type

The heart of Qwerty is the basis type, which facilitates intuitive, higher-
level programming without sacrificing efficiency. A basis in Qwerty represents
exactly the straighforward concept of an orthonormal basis taught in
undergraduate linear algebra courses (Axler, 2023), and Qwerty primitives for
state evolution and measurement are defined in terms of a basis.

##### Basis literals

Qwerty includes built-in bases such as the standard
$\left|0\right\rangle/\left|1\right\rangle$ basis (std), the
$\left|+\right\rangle/\left|-\right\rangle$ basis (pm), the
$\left|+i\right\rangle/\left|-i\right\rangle$ basis (ij)222In deference to
electrical engineers, Qwerty uses the literal ’j’ to represent
$\left|-i\right\rangle$., and the N-qubit Fourier basis (fourier[N]) (Nielsen
and Chuang, 2010). Programmers can construct more sophisticated bases by
wrapping lists of qubit literals in curly brackets; for example, {’0’,’1’} is
equivalent to std. On the other hand, {’0’, phase(theta)*’1’} is not, instead
representing the basis consisting of $\left|0\right\rangle$ and
$e^{i\theta}\left|1\right\rangle$.

⬇ ApplyToEach(H, q);

(a) Q#: Converting many qubits from the
$\left|0\right\rangle/\left|1\right\rangle$ basis to the
$\left|+\right\rangle/\left|-\right\rangle$ basis

⬇ std[N] >> pm[N]

(b) Qwerty: Converting N qubits from the
$\left|0\right\rangle/\left|1\right\rangle$ basis to the
$\left|+\right\rangle/\left|-\right\rangle$ basis

⬇ within { ApplyToEachA(H, q); ApplyToEachA(X, q); } apply { Controlled
Z(Most(q), Tail(q)); }

(c) Q#: The diffuser in Grover’s algorithm (Vasilevsky and Cortes, 2023),
which multiplies all $\left|+\right\rangle/\left|-\right\rangle$ basis states
by a negative phase except $\left|+\right\rangle^{\otimes n}$

⬇ -(’+’[N] >> -’+’[N])

(d) Qwerty: The diffuser in Grover’s algorithm, which multiplies all
$\left|+\right\rangle/\left|-\right\rangle$ basis states by a negative phase
except $\left|+\right\rangle^{\otimes n}$

Figure 3. Side-by-side comparison of typical operations in gate-oriented
languages versus their more expressive equivalents in Qwerty.

##### Translation

Unitary state evolution in Qwerty is written using a basis translation,
written $\mathrm{basis}_{\mathrm{in}}$ >>$\mathrm{basis}_{\mathrm{out}}$. Fig.
3 shows some examples. For two bases $\mathrm{basis}_{\mathrm{in}}$ and
$\mathrm{basis}_{\mathrm{out}}$ that span the same (sub)space of $m$ qubits,
the basis translation $\mathrm{basis}_{\mathrm{in}}$
>>$\mathrm{basis}_{\mathrm{out}}$ performs the following transformation:

$\displaystyle\alpha_{1}\left|\mathrm{basis}_{\mathrm{in}}^{(1)}\right\rangle+\alpha_{2}\left|\mathrm{basis}_{\mathrm{in}}^{(2)}\right\rangle+\cdots+\alpha_{n}\left|\mathrm{basis}_{\mathrm{in}}^{(n)}\right\rangle$
$\displaystyle\Downarrow$
$\displaystyle\alpha_{1}\left|\mathrm{basis}_{\mathrm{out}}^{(1)}\right\rangle+\alpha_{2}\left|\mathrm{basis}_{\mathrm{out}}^{(2)}\right\rangle+\cdots+\alpha_{n}\left|\mathrm{basis}_{\mathrm{out}}^{(n)}\right\rangle$

Basis translations can operate on subspaces, as shown in Fig. 3d, where the
basis {’+’[N]} (written without braces as ’+’[N] as syntactic sugar) indicates
that the translation ’+’[N] >> -’+’[N] acts only on the subspace spanned by
$\left|+\right\rangle^{\otimes N}$ — specifically, it maps
$\left|+\right\rangle^{\otimes N}\mapsto-\left|+\right\rangle^{\otimes}$ and
leaves other pm[N] basis states alone.

The basis translation primitive in Qwerty simplifies many popular operations
in quantum algorithms — for instance, quantum Fourier transform (QFT) is
performed with simply std[N] >> fourier[N]. Furthermore, this abstraction is
cheap because translations map well to multi-controlled gates. (For a rigorous
definition of the semantics of basis translations, see Appendix A.)

##### Translation syntactic sugar

For convenience, Qwerty includes $b$.flip and $b$.rotate($\theta$) constructs
for every basis $b$ that spans the full one-qubit space. $b$.flip swaps the
basis vectors of $b$, and $b$.rotate($\theta$) rotates around $b$ by $\theta$
radians. For example, std.flip is equivalent to std >> {’1’,’0’}, and
std.rotate(theta) is compiled to . Both examples coincide exactly with the $X$
and $R_{z}(\theta)$ gates, respectively (Nielsen and Chuang, 2010).

To facilitate further expressiveness, Qwerty also includes $q\ell$.prep, where $q\ell$ is a qubit literal (Section 3.2.1). This construct allows access to the plumbing by which the compiler lowers qubit literals. For example, an ordinary qubit literal ’10+’ is equivalent to ’000’ | ’10+’.prep, which in turn is equivalent to ’000’ | std.flip+id+(std>>pm). Observe that ’10+’.prep is much easier to read than std.flip+id+(std>>pm), and the expected input state (’000’) is more explicit.

⬇ MResetZ(q);

(a) Q#: Measuring in the $\left|0\right\rangle/\left|1\right\rangle$ basis

⬇ std.measure

(b) Qwerty: Measuring in the $\left|0\right\rangle/\left|1\right\rangle$ (std)
basis

⬇ Adjoint QFT(q); ForEach(MResetZ, q);

(c) Q#: Measuring in the Fourier basis

⬇ fourier[N].measure

(d) Qwerty: Measuring in the Fourier basis

Figure 4. Side-by-side comparison of measurements traditional languages versus
their equivalents in Qwerty.

##### Measurement

It is common to view qubit measurement as being performed in some basis
(Nielsen and Chuang, 2010, §2.2.5), e.g., the standard basis or the
$\left|+\right\rangle/\left|-\right\rangle$ basis. Rather than hard-coding
bases in the names of bespoke standard library functions for measurement as
languages like Q# do (with MResetZ, MResetX, etc.), Qwerty defines measurement
as an operation on a basis. Fig. 4 compares measurement in Qwerty with
measurement in traditional gate-oriented languages.

####  3.2.3. Reversible quantum functions

Many quantum subroutines such as phase estimation (Section 4.2.1) take black-
box quantum operations as input, eventually executing them backwards or in a
subspace. Qwerty includes features that facilitate this kind of modular
programming. However, these features require that the quantum operation
includes no qubit allocation, discarding, or measurement333Qubit allocation is
permitted in reversible quantum functions if allocated temporary qubits
(ancilla qubits) are discarded cleanly with discardz; see Section A.5 in
Appendix A.. (This is because it is absurd to un-measure a qubit, for
example.) We call such operations reversible quantum functions.

##### Execution in a subspace

If $b$ is a basis and $f$ is a reversible quantum function, then the syntax
$b$ &$f$ (or $f$ &$b$) yields a new function that executes $f$ in the subspace
identified by $b$. For example, the basis translation ’1’ + std >> ’1’ +
{’1’,’0’} can be written slightly more succinctly as ’1’ & std >> {’1’,’0’}
instead, as if the ’1’ portion of each basis was factored out. (Note that &
has lower precedence than >>.)

##### Running code backwards

If $f$ is a reversible quantum function, then ~$f$ is a function that runs $f$
backwards. For example, ~std.rotate(pi/4) is equivalent to std.rotate(-pi/4).

⬇ 1import sys 2from qwerty import * 3 4def bv(secret_string): 5 @classical[N](secret_string) 6 def f(secret_string: bit[N], x: bit[N]) -> bit: 7 return (secret_string & x).xor_reduce() 8 9 @qpu[N](f) 10 def kernel(f: cfunc[N,1]) -> bit[N]: 11 return ’+’[N] | f.phase \ 12 | pm[N] >> std[N] \ 13 | std[N].measure 14 15 return kernel() 16 17secret_string = bit.from_str(sys.argv[1]) 18print(bv(secret_string))
---
Figure 5. A full Python module including the Qwerty Bernstein–Vazirani code
from Fig. 1.

####  3.2.4. Quantum kernels

Using Qwerty, quantum kernels444Here, “kernel” is meant in the sense of an
accelerator kernel such as a CUDA kernel. are written as Python functions with
the @qpu annotation. Fig. 5 shows a full example of Bernstein–Vazirani written
in Qwerty. The contents of @qpu kernels use Qwerty syntax and are sent through
the Qwerty compiler. Specifically, they run on a quantum accelerator (or
simulator), not in the Python interpreter. Drawing such a separation between
Python and Qwerty code sidesteps complexities in analysis of Qwerty (Paykin et
al., 2017) and maintains the convenience of existing classical libraries for
e.g. numerical optimization.

##### Dimension variables

Quantum kernels may have dimension variables (e.g., the N on line 9 of Fig. 5)
to make them polymorphic in the number of qubits on which they operate. The
compiler attempts to infer dimension variable based on the type of captured
objects (e.g., the capture f of kernel(), specified on line 9 and whose type
is declared on line 10 of Fig. 5). When the compiler cannot infer a dimension
variable, such as N on line 5 of Fig. 6, the programmer must specify it using
[[$\ldots$]] notation as shown on line 10 of Fig. 6. (Instantiation with
[[$\ldots$]] can also be performed inside a quantum kernel, as used in line 12
of Fig. 13a.)

⬇ 1import sys 2from qwerty import * 3 4def ghz(n_qubits): 5 @qpu[N] 6 def kernel() -> bit[N]: 7 return ’+’ + ’0’[N-1] | ’1’ & std.flip[N-1] \ 8 | std[N].measure 9 10 return kernel[[n_qubits]](histogram=True, 11 shots=2048) 12 13n_qubits = int(sys.argv[1]) 14print_histogram(ghz(n_qubits)) 15# Prints: 16# 00000000 -> 49.37% 17# 11111111 -> 50.63%
---
Figure 6. Preparing the Greenberger–Horne–Zeilinger (GHZ) state (Greenberger
et al., 2007) in Qwerty. Measuring this entangled state yields either all 0s
(line 16) or all 1s (line 17).

⬇ Controlled Z(Most(q),Tail(q));

(a) Q#: Flag $11\cdots 1$ (all ones) as the answer using a multi-controlled
$Z$ gate (Vasilevsky and Cortes, 2023)

⬇ return x.and_reduce()

(b) Qwerty: Flag $11\cdots 1$ (all ones) as the answer by ANDing together all
input bits

Figure 7. Side-by-side comparison of a Grover’s oracle (criteria) that flags
$11\cdots 1$ as the answer written in both Q# versus Qwerty.

####  3.2.5. Classical embedding

Typically, quantum algorithms that solve classical problems execute classical
logic on qubits. For example, Bernstein–Vazirani (Section 3.1) invokes $f(x)$
on a special superposition, and Grover’s algorithm queries the search
criteria, a classical black box, on a superposition of possible answers
(Grover, 1996; Nielsen and Chuang, 2010). Although it is obvious that
classical logic is most easily programmed classically, gate-oriented
programming languages often require writing such classical logic as low-level
quantum gates. Fig. 7 compares a Grover’s oracle written in Qwerty with one
written in Q#. Note that x in Fig 7b has type bit[N] (N classical bits), not
qubit[N] (N qubits).

##### Classical functions

Classical functions are defined similarly to @qpu kernels and may also have
dimension variables and captures as seen on lines 5-7 of Fig. 5. Functions
decorated with @classical can be invoked from Python code to run them
classically inside the Python interpreter rather than on qubits.

##### Instantiation

To invoke a @classical function f on qubits, a quantum kernel must instantiate
f. The syntax f.xor_embed realizes f as a Bennett embedding (Bennett, 1989),
which has the well-known form
$B_{f}\left|x\right\rangle\left|y\right\rangle\triangleq\left|x\right\rangle\left|y\oplus
f(x)\right\rangle$. However, many algorithms expect some
$P_{f}\left|x\right\rangle\triangleq(-1)^{f(x)}\left|x\right\rangle$ instead,
which the syntax f.phase summons. (This abstracts away the implementation
detail of converting a Bennett embedding into this form using
$\left|-\right\rangle$ ancillas (Nielsen and Chuang, 2010, §6.1.1).) Finally,
if f is already reversible, as in the case of the multiplier used in Shor’s
(Rines and Chuang, 2018; Nielsen and Chuang, 2010), writing f.inplace(f_inv)
applies f in-place, i.e,.
$U_{f}\left|x\right\rangle\triangleq\left|f(x)\right\rangle$. Note that an
implementation of $f^{-1}$ (named f_inv for example) is currently required
(Bennett, 1989).

##  4\. Algorithms Expressed in Qwerty

This section shows Qwerty more concretely via Qwerty implementations of well-
known algorithms. All examples compile and run as-is using the Qwerty compiler
and runtime. However, some examples may contain more line breaks than typical
Python code in order to fit within page margins.

This section presents Qwerty implementations of the following algorithms:

  * •

§4.1: Oracle-based quantum algorithms

    * –

§4.1.1: Deutsch’s algorithm

    * –

§4.1.2: Deutsch–Jozsa algorithm

    * –

§4.1.3: Bernstein–Vazirani algorithm

    * –

§4.1.4: Quantum period finding

    * –

§4.1.5: Simon’s algorithm

  * •

§4.2: Algorithms for factoring integers

    * –

§4.2.1: Quantum phase estimation

    * –

§4.2.2: Quantum order finding

    * –

§4.2.3: Shor’s algorithm

  * •

§4.3: Quantum search algorithms

    * –

§4.3.1: Grover’s unstructured search

    * –

§4.3.2: Yoder–Low–Chuang fixed-point amplitude amplification

    * –

§4.3.3: Niroula–Nam string matching

(Examples begin on the next page and are intentionally laid out as one
algorithm per page for easier reader navigation.)

###  4.1. Oracle-Based Algorithms

Many quantum algorithms designed to solve classical problems operate by
running a classical black-box function (known as an oracle) on a superposition
state and measuring the outcome. We begin with some well-known members of this
group of algorithms because they include the most approachable examples.

####  4.1.1. Deutsch’s algorithm

Deutsch’s algorithm takes a black box function
$f:\\{0,1\\}\rightarrow\\{0,1\\}$ as input and determines whether $f$ is
constant using a single invocation of $f$ (Deutsch and Penrose, 1997; Cleve et
al., 1998; Nielsen and Chuang, 2010). Specifically, the algorithm returns
$f(0)\oplus f(1)$. Fig. 8a shows Deutsch’s algorithm and some example black
boxes implemented in Qwerty.

Wrapping algorithms in Python functions such as deutsch() on line 3 of Fig. 8a
is idiomatic Qwerty. This way, quantum kernels such as kernel() on line 5 of
Fig. 8a can capture algorithm inputs (e.g., f in Fig. 8a) or the results of
classical pre-processing. Wrapper functions may also perform classical post-
processing before returning (e.g., Deutsch–Jozsa in Section 4.1.2).

The notation cfunc on line 5 of Fig. 8a is shorthand for the type of a
function from bit to bit (func[[bit],bit]). Currently, Qwerty requires
specifying the type of all captures (f in this case).

Line 6 of Fig. 8a performs the following steps:

  1. (1)

Prepare $\left|+\right\rangle$ via the qubit literal ’+’.

  2. (2)

Apply $\left|x\right\rangle\mapsto(-1)^{f(x)}\left|x\right\rangle$, where
$x\in\\{0,1\\}$, using f.phase (see Section 3.2.5).

  3. (3)

Measure in the $\left|+\right\rangle/\left|-\right\rangle$ (plus/minus) basis
with pm.measure. Measuring $\left|+\right\rangle$ or $\left|-\right\rangle$
yields classical bits 0 and 1, respectively.

The | operator used on line 6 of Fig. 8a is a pipe, analogous to a Unix shell pipe. Qubits flow left-to-right through Qwerty pipelines.

Fig. 8b shows some Python code for invoking the Qwerty code from Fig. 8a. Line
1 of Fig. 8b defines naive_classical(), an equivalent classical implementation
that performs two invocations of f rather than the single invocation required
by the quantum algorithm. This demonstrates that Qwerty @classical functions
(e.g., lines 11 and 15 of Fig. 8a) may be invoked classically from Python,
which is useful for testing.

⬇

1from qwerty import *

2

3def deutsch(f):

4 @qpu(f)

5 def kernel(f: cfunc) -> bit:

6 return ’+’ | f.phase | pm.measure

7

8 return kernel()

9

10@classical

11def balanced(x: bit) -> bit:

12 return ~x

13

14@classical

15def constant(x: bit) -> bit:

16 return bit[1](0b1)

(a) Qwerty code for Deutsch’s algorithm

⬇

7def naive_classical(f):

8 return f(bit[1](0b0)) \

9 ^ f(bit[1](0b1))

10

11print(’Balanced f:’)

12print(’Classical: f(0) xor f(1) =’,

13 naive_classical(balanced))

14print(’Quantum: f(0) xor f(1) =’,

15 deutsch(balanced))

16

17print(’\nConstant f:’)

18print(’Classical: f(0) xor f(1) =’,

19 naive_classical(constant))

20print(’Quantum: f(0) xor f(1) =’,

21 deutsch(constant))

(b) Python for testing Deutsch’s algorithm

Figure 8. Deutsch’s algorithm in Qwerty

####  4.1.2. Deutsch–Jozsa algorithm

The Deutsch–Jozsa algorithm is a generalization of Deutsch’s algorithm
(Section 4.1.1). The input remains a black-box classical function $f$, except
$f$ has $N$ input bits instead of 1. $f$ is assumed to be either constant or
balanced (returning 0 for exactly half its domain) (Deutsch and Jozsa, 1997;
Cleve et al., 1998; Nielsen and Chuang, 2010); the algorithm determines
whether $f$ is constant or balanced using a single invocation of $f$.

Compared to line 4 of Fig. 8a, line 4 of Fig. 9a introduces the syntax [N] in
@qpu[N]. Here, N is a dimension variable allowing the programmer to specify
dimensions in terms of N rather than hard-coding fixed numbers. For example,
on line 7 of Fig. 9a, the syntax ’+’[N] prepares N duplicate
$\left|+\right\rangle$ states side-by-side. If N${}=3$, for instance, then
this expression would expand to ’+’[3] or equivalently ’+++’.

However, the code in Fig. 9a never explicitly specifies N, because the
compiler can infer N. Specifically, the portion f: cfunc[N,1] of line 5 of
Fig. 9a instructs the compiler to infer $N$ from the number of input bits of
the capture f. (The type cfunc[N,1] is syntactic sugar for the more verbose
func[[bit[N]],bit[1]], which means a function whose arguments are only a
bit[N] and whose result is a bit[1].)

Lines 7-8 of Fig. 9a are the quantum portion of the algorithm. The pipeline
shown does the following:

  1. (1)

Prepare $\left|+\right\rangle^{\otimes N}$.

  2. (2)

Apply $\left|x\right\rangle\mapsto(-1)^{f(x)}\left|x\right\rangle$, where
$x\in\\{0,1\\}^{N}$ (see Section 3.2.5).

  3. (3)

Measure in the $N$-qubit plus/minus
($\left|+\right\rangle/\left|-\right\rangle$) basis, called pm in Qwerty.

In the last step, measuring $\left|+\right\rangle^{\otimes N}$ yields
classical bits $00\cdots 0$. (Measuring in pm[N] aligns with Deutsch and
Jozsa’s original formulation (Deutsch and Jozsa, 1997).)

The x.xor_reduce() operation on line 24 of Fig. 9a XORs all bits of x
together, producing a single-bit result.

Fig. 9b shows Python code for invoking the Qwerty Deutsch–Jozsa code written
in Fig. 9a. For brevity, we assume all of Fig. 9 resides in the same Python
module (.py file), but Fig. 9b could also import Fig. 9a if desired, as both
can be typical Python modules.

⬇

1from qwerty import *

2

3def deutsch_jozsa(f):

4 @qpu[N](f)

5 def kernel(f: cfunc[N,1]) \

6 -> bit[N]:

7 return ’+’[N] | f.phase \

8 | pm[N].measure

9

10 if int(kernel()) == 0:

11 return ’constant’

12 else:

13 return ’balanced’

14

15@classical

16def constant(x: bit[4]) -> bit:

17 # f(x) = 1

18 return bit[1](0b1)

19

20@classical

21def balanced(x: bit[4]) -> bit:

22 # f(x) = 1 for half the inputs

23 # and f(x) = 0 for the other half

24 return x.xor_reduce()

(a) Qwerty code for the Deutsch–Jozsa algorithm

⬇

6def naive_classical(f, n_bits):

7 answers = [0, 0]

8 for i in range(2**(n_bits-1)+1):

9 answer = int(f(bit[n_bits](i)))

10 answers[answer] += 1

11

12 if 0 in answers:

13 return ’constant’

14 else:

15 return ’balanced’

16

17print(’Constant test:’)

18print(’Classical:’,

19 naive_classical(constant, 4))

20print(’Quantum:’,

21 deutsch_jozsa(constant))

22

23print(’\nBalanced test:’)

24print(’Classical:’,

25 naive_classical(balanced, 4))

26print(’Quantum:’,

27 deutsch_jozsa(balanced))

(b) Python for testing the Deutsch–Jozsa algorithm

Figure 9. Deutsch–Jozsa algorithm in Qwerty

####  4.1.3. Bernstein–Vazirani algorithm

Section 3.1 describes Bernstein–Vazirani (Bernstein and Vazirani, 1993; Fallek
et al., 2016), with Fig. 1 showing the steps of the algorithm.

Unlike the previous examples of Deutsch’s (Fig. 8a) and Deutsch–Jozsa (Fig.
9a), Fig. 10a shows the use of a basis translation on line 8. The syntax pm[N]
>> std[N] performs a basis translation from the $N$-qubit plus/minus basis
(pm[N]) to the $N$-qubit standard basis (std[N]). For each qubit, this
performs the mapping $\left|+\right\rangle\mapsto\left|0\right\rangle$ and
$\left|-\right\rangle\mapsto\left|1\right\rangle$.

Writing pm is shorthand for the basis literal {’+’,’-’}, and similarly std is
syntactic sugar for {’0’,’1’}. Thus, pm[N] >> std[N] behaves identically to
{’+’,’-’}[N] >> {’0’,’1’}[N], a more verbose form where the element-wise
translation ’+’$\mapsto$’0’ and ’-’$\mapsto$’1’ is more explicit.

The [N] suffix takes the repeated tensor product of an expression (such as a
basis) N times. For example, if N${}=2$, then {’0’,’1’}[N] becomes
{’0’,’1’}+{’0’,’1’}. This [N] syntax applies to functions as well: the code
({’+’,’-’} >>{’0’,’1’})[N] is also equivalent to the operation performed by
line 8 of Fig. 10a, as would be (pm >>std)[N].

Furthermore, lines 8 and 9 in Fig. 10a are exactly equivalent to pm[N].measure in Deutsch–Jozsa (line 8 of Fig. 9a). This is true because any $b$.measure where $b$ is an N-qubit non-std basis compiles to ($b$>>std[N]) | std[N].measure.

Fig. 10b shows Python code for invoking the Qwerty code in Fig. 10a, including
a naïve classical implementation (line 3) which requires $N$ invocations of
the black box f rather than just one. The classical code demonstrates that the
bit class included in the Qwerty Python runtime can conveniently be sliced
like a list (line 7 of Fig. 10b) or manipulated with bitwise operations like
an int (line 8 of Fig. 10b).

⬇

1from qwerty import *

2

3def bv(f):

4 @qpu[N](f)

5 def kernel(f: cfunc[N,1]) \

6 -> bit[N]:

7 return ’+’[N] | f.phase \

8 | pm[N] >> std[N] \

9 | std[N].measure

10

11 return kernel()

12

13def get_black_box(secret_string):

14 @classical[N](secret_string)

15 def f(secret_string: bit[N],

16 x: bit[N]) -> bit:

17 return (secret_string & x) \

18 .xor_reduce()

19

20 return f

(a) Qwerty code for the Bernstein–Vazirani algorithm

⬇

3import sys

4

5def naive_classical(f, n_bits):

6 secret_found = bit[n_bits](0b0)

7 x = bit[n_bits](0b1 << (n_bits-1))

8 for i in range(n_bits):

9 secret_found[i] = f(x)

10 x = x >> 1

11 return secret_found

12

13secret_str = \

14 bit.from_str(sys.argv[1])

15n_bits = len(secret_str)

16black_box = get_black_box(secret_str)

17

18print(’Classical:’,

19 naive_classical(black_box,

20 n_bits))

21print(’Quantum:’, bv(black_box))

(b) Python for testing the Bernstein–Vazirani algorithm

Figure 10. Bernstein–Vazirani algorithm in Qwerty

####  4.1.4. Period finding

Given a black box function $f:\\{0,1\\}^{M}\rightarrow\\{0,1\\}^{N}$ as input,
the quantum period finding algorithm returns the smallest positive $r$ such
that $f(x)=f(x+r)$, i.e., the period of $f$ (Mosca, 1999; Nielsen and Chuang,
2010).

Lines 8-11 of Fig. 11a specify the quantum subroutine. The pipeline does the
following:

  1. (1)

Prepare $\left|+\right\rangle^{\otimes M}\left|0\right\rangle^{\otimes N}$.

  2. (2)

Apply
$\left|x\right\rangle\left|y\right\rangle\mapsto\left|x\right\rangle\left|y\oplus
f(x)\right\rangle$. (Observe the XOR, $\oplus$, that is the namesake for the
syntax f.xor_embed used.)

  3. (3)

Measure the first register in the $M$-qubit Fourier basis (Nielsen and Chuang,
2010, §5.1) and discard the second register.

By explicitly requesting to project the first register to an $M$-qubit Fourier
basis state, line 10 is more expressive than gate-oriented code, which would
manually invoke the inverse quantum Fourier transform (IQFT) and measure in
the $\left|0\right\rangle/\left|1\right\rangle$ basis. By contrast, the Qwerty
compiler automatically synthesizes the same code (specifically
fourier[N]>>std[N]|std[N].measure) as discussed in Section 4.1.3.

Qwerty allows taking tensor products of functions, such as fourier[M].measure
(line 10 of Fig. 11a) and discard[N] (line 11 of Fig. 11a). Calling the
resulting function, written as
fourier[M].measure + discard[N], does the following: (1) splits the input
tuple of $M+N$ qubits into two tuples of $M$ and $N$ bits, respectively; (2)
runs both functions independently; and (3) merges their result tuples: in this
example, the tuple with $M$ bits (returned by
fourier[M].measure) is concatenated with the empty tuple () (returned by
discard[N]). The resulting value is a tuple of $M$ bits, which explains why
the return value of kernel() written on line 7 of Fig. 11a is bit[M].

The Qwerty Python runtime contains some convenience functions for post-
processing. For example, bit[M].as_bin_frac() (used on lines 14 and 15 of Fig.
11a) returns a Python fractions.Fraction instance (Python Software Foundation,
2024) representing the bits interpreted as a binary fraction (Nielsen and
Chuang, 2010, §5.1).

Fig. 11b shows classical Python code that invokes the Qwerty code in Fig. 11a.
The particular $f$ used in this example (line 24 of Fig. 11a) returns the
zero-extended lower $K$ bits of the input string, making the period $2^{K}$.
The [[$\cdots$]] syntax on lines 27-29 of Fig. 11a instantiates f with its
dimension variables M, N, and K set to the desired values (see Section 3.2.4).

⬇

1import math

2from qwerty import *

3

4def period_finding(black_box):

5 @qpu[M,N](black_box)

6 def kernel(black_box: cfunc[M,N]) \

7 -> bit[M]:

8 return ’+’[M] + ’0’[N] \

9 | black_box.xor_embed \

10 | fourier[M].measure \

11 + discard[N]

12

13 result1, result2 = kernel(shots=2)

14 l_over_r1 = result1.as_bin_frac()

15 l_over_r2 = result2.as_bin_frac()

16 r = math.lcm(l_over_r1.denominator,

17 l_over_r2.denominator)

18 return r

19

20def get_black_box(n_bits_in,

21 n_bits_out,

22 n_mask_bits):

23 @classical[M,N,K]

24 def f(x: bit[M]) -> bit[N]:

25 return bit[N-K](0b0), x[M-K:]

26

27 return f[[n_bits_in,

28 n_bits_out,

29 n_mask_bits]]

(a) Qwerty code for period finding

⬇

5n_bits_in = int(sys.argv[1])

6n_bits_out = int(sys.argv[2])

7n_masked = int(sys.argv[3])

8black_box = get_black_box(n_bits_in,

9 n_bits_out,

10 n_masked)

11if period_finding(black_box) \

12 == 2**n_masked:

13 print(’success!’)

14else:

15 print(’oops...’)

(b) Python for testing period finding

Figure 11. Period finding in Qwerty

####  4.1.5. Simon’s algorithm

Suppose a 2-to-1 classical function $f:\\{0,1\\}^{N}\rightarrow\\{0,1\\}^{N}$
satisfies $f(x)=f(y)\Rightarrow x=y\oplus s$ when $x\neq y$. Given a black-box
implementation of $f$, Simon’s algorithm returns the secret string $s$ (Simon,
1994, 1997).

Fig. 12a is the first example shown making use of id, the identity operation
on a qubit. It has the type of a function from one qubit to one qubit, so
id[N] has the type of a function from qubit[N] to qubit[N].

Also in contrast with previous examples presented, Simon’s algorithm requires
multiple invocations of the quantum kernel (kernel() on lines 6-13 of Fig.
12a). Specifically, each nonzero measurement becomes a row of an
$(N{-}1){\times}N$ matrix of bits (lines 15-22 of Fig. 12a). For the sake of
brevity, we relegate the Python code performing Gaussian elimination on this
matrix to a different module not shown here (imported on line 2 of Fig. 12a).
This post-processing can be implemented efficiently using existing highly-
optimized Python libraries such as numpy (Harris et al., 2020).

The whole algorithm may need to be retried if this classical post-processing
fails; this is accomplished by simon_post() throwing a Retry exception and
line 25 catching it. Ordinary Python exception handling works here, with no
new quantum-specific features needed.

The classical logic on lines 32-34 of Fig. 12a was determined by writing out
the truth table for an example function obeying the property stated at the
beginning of this section and solving 3 Karnaugh maps. Writing this black box
as classical logic only once is more convenient than hand-writing separate
quantum and classical oracles and manually proving their behavior matches.

The Python code invoking Simon’s in Fig. 12b includes a classical solution
that demonstrates — at least informally — the exponential speedup of Simon’s
algorithm over classical algorithms (Simon, 1994): compare the $O(2^{N})$
classical loop on line 3 of Fig. 12b with the polynomial-time quantum code
(Fig. 12a).

⬇

1from qwerty import *

2from simon_post import simon_post, \

3 Retry

4

5def simon(f):

6 @qpu[N](f)

7 def kernel(f: cfunc[N]) -> bit[N]:

8 return ’+’[N] + ’0’[N] \

9 | f.xor_embed \

10 | (std[N] >> pm[N]) \

11 + id[N] \

12 | std[N].measure \

13 + discard[N]

14

15 while True:

16 rows = []

17 while True:

18 row = kernel()

19 if int(row) != 0:

20 rows.append(row)

21 if len(rows) >= row.n_bits-1:

22 break

23 try:

24 return simon_post(rows)

25 except Retry:

26 print(’retrying...’)

27 continue

28

29@classical

30def black_box(q: bit[3]) -> bit[3]:

31 return \

32 (~q[0]& q[2]|q[0]&~q[2]|~q[1],

33 ~q[0]&~q[2]|q[0]& q[2],

34 ~q[0]&~q[2]|q[0]& q[2]|~q[1])

(a) Qwerty code for Simon’s algorithm

⬇

5def naive_classical(f, n_bits):

6 out_to_x = {}

7 for i in range(2**n_bits):

8 x = bit[n_bits](i)

9 out = f(x)

10 if out in out_to_x:

11 return x ^ out_to_x[out]

12 out_to_x[out] = x

13

14print(’Classical:’,

15 naive_classical(black_box, 3))

16print(’Quantum:’, simon(black_box))

(b) Python for testing Simon’s algorithm

Figure 12. Simon’s algorithm in Qwerty

###  4.2. Factoring

The excitement sparked by Shor’s 1994 discovery of an efficient quantum
algorithm for factoring integers (Shor, 1994, 1999) still fuels interest in
quantum computing today. This section shows how to factor in Qwerty using
phase estimation as described by Cleve et al. (Cleve et al., 1998) and Nielsen
and Chuang (Nielsen and Chuang, 2010).

####  4.2.1. Quantum phase estimation

Unlike previous examples, quantum phase estimation (QPE) is primarily a
building block on which other algorithms are built. QPE finds an eigenvalue of
a provided operator (up to some precision); specifically, provided a unitary
$U$ and state $\left|u\right\rangle$ such that
$U\left|u\right\rangle=e^{i\varphi}\left|u\right\rangle$, QPE estimates
$\varphi$ (Cleve et al., 1998; Nielsen and Chuang, 2010).

The parameter prep_eigvec (lines 3 and 7 of Fig. 13a) is a function responsible for preparing the eigenvector $\left|u\right\rangle$. The syntax prep_eigvec() used on line 10 of Fig. 13a is syntactic sugar for calling prep_eigvec with an empty tuple as an argument, i.e., () | prep_eigvec.

QPE repeatedly applies $U$ raised to increasing powers of 2, i.e.,
$U^{2^{0}}$, then $U^{2^{1}}$, then $U^{2^{2}}$, and so on. An efficient $U$
will effect this exponentiation without exponential cost (e.g., line 15 of
Fig. 13b). The Qwerty formulation facilitates this by making the exponent $j$
of $U^{2^{j}}$ a dimension variable of op (see Section 3.2.4), specifically a
free dimension variable. The syntax [[...]] on line 8 of Fig. 13a indicates
that op ($U$) has a free dimension variable, and line 12 uses [[j]] to
instantiate op with the free dimension variable set to j, thus instantiating
$U^{2^{j}}$ efficiently. Lines 10-15 of Fig. 13b show how op could be
implemented — note that J is a free dimension variable.

To achieve repeated applications of $U^{2^{j}}$ without hard-coding some fixed
number of them, Qwerty supports loop-like repeated applications as written in
line 11-13 in Fig. 13a. The point of these repeated applications is to
approximate a Fourier basis state which line 14 of Fig. 13a will identify. Yet
to accomplish this, $U^{2^{j}}$ must be applied in different subspaces.
Because op ($U$) is a black box, though, typical syntax for restricting a
basis translation to a subspace (e.g., Fig. 3d) is not applicable. Thus, as
discussed in Section 3.2.3, the operator & used in lines 11-12 of Fig. 13a
runs $U^{2^{j}}$ in individual ’1’ subspaces from right to left. Note that the
std[$\cdots$]s on line 11 are effectively padding, since running in both the
’0’ and ’1’ subspaces means running on the whole space.

Fig. 13b shows an example of using QPE.

⬇

1from qwerty import *

2

3def qpe(precision, prep_eigvec, op,

4 n_shots):

5 @qpu[M,T](prep_eigvec, op)

6 def kernel(

7 prep_eigvec: qfunc[0,M],

8 op: rev_qfunc[M][[...]]) \

9 -> bit[T]:

10 return ’+’[T] + prep_eigvec() \

11 | (std[T-1-j]+’1’+std[j]

12 & op[[j]]

13 for j in range(T)) \

14 | fourier[T].measure \

15 + discard[M]

16

17 k_inst = kernel[[precision]]

18 for meas in k_inst(shots=n_shots):

19 yield meas.as_bin_frac()

(a) Qwerty code for quantum phase estimation

⬇

3import sys

4

5phi = float(sys.argv[1])

6precision = int(sys.argv[2])

7

8@qpu

9def prep1() -> qubit:

10 return ’1’

11

12@qpu[J](phi)

13@reversible

14def rot(phi: angle,

15 q: qubit) -> qubit:

16 return q | std >> \

17 {’0’, phase(2*pi*phi*2**J)*’1’}

18

19print(’Expected:’, phi)

20phi_got, = qpe(precision, prep1, rot,

21 n_shots=1)

22print(’Actual:’, float(phi_got))

(b) Qwerty for testing quantum phase estimation

Figure 13. Quantum phase estimation in Qwerty

####  4.2.2. Order finding

⬇

4import sys

5

6def naive_classical(x, modN):

7 for r in range(1, modN):

8 if x**r % modN == 1:

9 return r

10

11err = 0.2

12x = int(sys.argv[1])

13modN = int(sys.argv[2])

14if math.gcd(x, modN) != 1:

15 raise ValueError(’invalid x, modN’)

16

17print(’Classical:’,

18 naive_classical(x, modN))

19print(’Quantum:’,

20 order_finding(err, x, modN))

Figure 14. Python for testing order finding

A key ingredient of Shor’s factoring algorithm, quantum order finding
determines the multiplicative order of $x$ modulo $N$, which is defined as the
smallest positive integer $r$ such that $x^{r}\equiv 1\pmod{N}$. Here, $x$ and
$N$ are coprime positive integers (Rosen, 2010; Nielsen and Chuang, 2010).

Although it is possible to implement order finding using period finding
(Section 4.1.4) instead (Shor, 1994, 1999; Nielsen and Chuang, 2010), the
Qwerty code in Fig. 15 calls out to QPE (Section 4.2.1) on line 22. The
operator mult passed to QPE is an in-place multiplier
$\left|y\right\rangle\mapsto\left|xy\bmod N\right\rangle$ (line 21), and the
eigenvector is an intricate superposition that (incredibly) is equal to
$\left|00\cdots 0\right\rangle\otimes\left|1\right\rangle$ (lines 10-12 in
Fig. 15) (Cleve et al., 1998; Nielsen and Chuang, 2010). (The calculations for
necessary QPE precision and qubit count on lines 6-8 of Fig. 15 are due to
Nielsen and Chuang (Nielsen and Chuang, 2010).)

The in-place multiplier is straightforward to define in Qwerty. Lines 14-16 of
Fig. 15 define a classical function xymodN that multiplies its input $y$ times
$x^{2^{j}}$ modulo $N$ ($x$, $j$, and $N$ are dimension variables defined on
line 14). Assuming the input $y$ is already a least positive residue modulo
$N$, xymodN is reversible because it permutes the least positive residues
modulo $N$. Thus, it can be instantiated in-place as desired (line 21 of Fig.
15). As noted in Section 3.2.5, though, Qwerty currently requires a reverse
implementation as well. Thankfully, undoing the multiplication by $x$ only
means multiplying by the modular inverse $x^{-1}$ instead. Lines 19 and 20
instantiate the forward and reverse multipliers, respectively (see Section
3.2.4). The ellipses ... on each line ask Qwerty to leave J as a free
dimension variable as qpe() expects (Section 4.2.1).

The classical post-processing makes use of the cfrac (continued fraction) type
included in the Qwerty Python runtime to convert the fractions.Fraction
(Python Software Foundation, 2024) returned by qpe() to a continued fraction
and choose a convergent. Choosing the last convergent whose denominator is
less than $N$ (lines 24-29 of Fig. 15) is due to Watkins (Watkins, 2023), and
taking the least common multiple (line 31 of Fig. 15) is due to Nielsen and
Chuang (Nielsen and Chuang, 2010).

Fig. 14 shows some Python code for invoking the order_finding() subroutine
from Fig. 15.

⬇

1import math

2from qwerty import *

3from qpe import qpe

4

5def order_finding(epsilon, x, modN):

6 L = math.ceil(math.log2(modN))

7 t = 2*L + 1 + math.ceil(

8 math.log2(2+1/(2*epsilon)))

9

10 @qpu[M]

11 def one() -> qubit[M]:

12 return ’0’[M-1] + ’1’

13

14 @classical[X,N,M,J]

15 def xymodN(y: bit[M]) -> bit[M]:

16 return X**2**J * y % N

17

18 x_inv = pow(x, -1, modN)

19 fwd = xymodN[[x,modN,L,...]]

20 rev = xymodN[[x_inv,modN,L,...]]

21 mult = fwd.inplace(rev)

22 frac1, frac2 = qpe(t, one, mult, 2)

23

24 def denom(frac):

25 cf = cfrac.from_fraction(frac)

26 for c in reversed(

27 cf.convergents()):

28 if c.denominator < modN:

29 return c.denominator

30

31 return math.lcm(denom(frac1),

32 denom(frac2))

Figure 15. Qwerty code for order finding

####  4.2.3. Shor’s algorithm

Shor’s algorithm finds a nontrivial factor of a positive integer $N$ (i.e., a
factor other than 1 or $N$). It achieves this using a reduction from factoring
to order finding (Section 4.2.2) (Shor, 1999; Nielsen and Chuang, 2010). In
other words, Shor’s algorithm is typically classical code that calls out to a
quantum order finding subroutine (Section 4.2.2). Consequently, Fig. 16a is
purely Python code, although it calls order_finding() (Fig. 15) on line 18.

Because it consists entirely of Python, this implementation of Shor’s itself
resembles the pseudocode from Nielsen and Chuang (Nielsen and Chuang, 2010,
§5.3.2). Also in Python is Fig. 16b, an example command-line program invoking
the algorithm.

⬇

1import math

2import random

3from qwerty import *

4

5from order_finding import \

6 order_finding

7

8def shors(epsilon, num):

9 if num % 2 == 0:

10 return 2

11

12 x = random.randint(2, num-1)

13 if (y := math.gcd(x, num)) > 1:

14 print(’Got lucky! Skipping ’

15 ’quantum subroutine...’)

16 return y

17

18 r = order_finding(epsilon, x, num)

19

20 if r % 2 == 0 \

21 and pow(x, r//2, num) != -1:

22 if (gcd := math.gcd(x**(r//2)-1,

23 num)) > 1:

24 return gcd

25 if (gcd := math.gcd(x**(r//2)+1,

26 num)) > 1:

27 return gcd

28

29 raise Exception("Shor’s failed")

(a) Python code for Shor’s algorithm

⬇

4import sys

5

6err = 0.2

7num = int(sys.argv[1])

8print(’Nontrivial factor of’, num,

9 ’is’, shors(err, num))

(b) Python for testing Shor’s algorithm

Figure 16. Shor’s algorithm in Qwerty

###  4.3. Search

Often, a strategy to take advantage of program structure using quantum
mechanical properties is unknown — this is where unstructured search is most
useful (Aaronson, 2022). This section shows how search can be implemented in
Qwerty and ends with an example of unstructured search in action.

####  4.3.1. Grover’s algorithm

Given a black box implementing $f:\\{0,1\\}^{N}\rightarrow\\{0,1\\}$ (i.e., an
oracle), Grover’s algorithm finds all $x\in\\{0,1\\}^{N}$ such that $f(x)=1$
(i.e., all answers to the oracle). The algorithm consists of many iterations,
each of which consists of the oracle followed by a special reflection called
the Grover diffuser. Applying the right number of iterations is crucial and
depends on the number of answers (Grover, 1996, 1997; Boyer et al., 1998;
Nielsen and Chuang, 2010).

A single Grover iteration is shown on lines 5-10 of Fig. 17a. Line 9 of Fig.
17a applies the transformation
$\left|x\right\rangle\mapsto(-1)^{f(x)}\left|x\right\rangle$ (see Section
3.2.5), and line 10 performs the diffuser from Fig. 3d.

Lines 16-17 of Fig. 17a apply I iterations of Grover’s starting with the equal
superposition ’+’[N]. (In Python, _ is common variable name for an unused
value, such as the loop variable in this case.) The [[n_iter]] syntax on line
20 of Fig. 17a instantiates kernel() with the proper number of iterations,
which may be calculated with the Python code starting at line 25 of Fig. 17a
(an implementation of a formula due to Nielsen and Chuang (Nielsen and Chuang,
2010, §6.1.4)). The measurements are post-processed on lines 22-23 of Fig. 17a
by invoking the oracle classically to filter out incorrect output.

Fig. 17b shows an example of running Grover’s algorithm. The oracle all_ones()
on lines 3-5 of Fig. 17b ANDs all bits of the input x together, thus
outputting 1 only for the input $11\cdots 1$.

⬇

1import math

2from qwerty import *

3

4def grover(oracle, n_iter, n_shots):

5 @qpu[N](oracle)

6 def grover_iter(oracle: cfunc[N,1],

7 q: qubit[N]) \

8 -> qubit[N]:

9 return q | oracle.phase \

10 | -(’+’[N] >> -’+’[N])

11

12 @qpu[N,I](grover_iter)

13 def kernel(grover_iter: qfunc[N]) \

14 -> bit[N]:

15 return \

16 ’+’[N] | (grover_iter

17 for _ in range(I)) \

18 | std[N].measure

19

20 kern_inst = kernel[[n_iter]]

21 results = kern_inst(shots=n_shots)

22 return {r for r in set(results)

23 if oracle(r)}

24

25def get_n_iter(n_qubits, n_answers):

26 n = 2**n_qubits

27 m = n_answers

28 theta = 2*math.acos(

29 math.sqrt((n-m)/n))

30 rnd = lambda x: math.ceil(x-0.5)

31 return rnd(math.acos(

32 math.sqrt(m/n))/theta)

(a) Qwerty code for Grover’s algorithm

⬇

3import sys

4

5@classical[N]

6def all_ones(x: bit[N]) -> bit:

7 return x.and_reduce()

8n_ans = 1

9

10n_qubits = int(sys.argv[1])

11oracle = all_ones[[n_qubits]]

12n_iter = get_n_iter(n_qubits, n_ans)

13answers = grover(oracle, n_iter,

14 n_shots=32)

15for answer in answers:

16 print(answer)

(b) Qwerty for testing Grover’s algorithm

Figure 17. Grover’s algorithm in Qwerty

####  4.3.2. Fixed-point amplitude amplification

⬇

3import sys

4

5@qpu[N]

6@reversible

7def a(q: qubit[N]) -> qubit[N]:

8 return q | ’+’[N].prep

9

10@classical[N]

11def oracle_(x: bit[N]) -> bit:

12 return ~x[:N-1].and_reduce()

13

14n_qubits = int(sys.argv[1])

15oracle = oracle_[[n_qubits]]

16orig_prob = 1/2**n_qubits

17res = fix_pt_amp(a, oracle,

18 orig_prob, 0.98,

19 histogram=True)

20print_histogram(res)

21# Prints:

22# 00 -> 48.93%

23# 01 -> 49.46%

24# 10 -> 0.44%

25# 11 -> 1.17%

Figure 18. Qwerty for testing fixed-point amplitude amplification

Despite its historical significance, Grover’s algorithm suffers from practical
difficulties: first, it may malfunction if more than half of the search space
are answers (Nielsen and Chuang, 2010). Second, implementers are struck with a
“soufflé problem” (Brassard, 1997): it is easy to ‘overcook’ the delicate
state by applying too many Grover iterations or ‘undercook’ it by applying too
few. Applying the right number of iterations requires knowing the number of
answers, which may be impractical. Yoder, Low, and Chuang propose a fixed-
point search algorithm (Yoder et al., 2014) that addresses these issues.

The algorithm is perhaps most easily understood as a special case of the
quantum singular value transform (QSVT) (Gilyén et al., 2019; Martyn et al.,
2021). Lines 18-21 of Fig. 19 rotate around the space of answers, and lines
22-27 rotate around the initial state (which a prepares). The particular
rotation angles are quite technical and depend on the lower bound for the
number of answers and the acceptable error; the separate fix_pt_phases module
(imported on line 2 of Fig 19) uses the existing pyqsp Python library to
generate these phases (Martyn et al., 2021).

Line 22 of Fig. 19 uses ~a to un-prepare the initial state. The @reversible
decorator on line 4 of Fig. 18 facilitates this by requiring that a() has no
irreversible operations (Section 3.2.3).

Fig. 18 shows a test invocation of the algorithm with an oracle identifying
states whose first $N-1$ bits are not all 1s. The original probability on line
14 is a drastic under-estimate, yet the result is not overcooked (lines 20-23
of Fig. 18).

⬇

1from qwerty import *

2from fix_pt_phases import get_phases

3

4def fix_pt_amp(a, oracle, orig_prob,

5 new_prob=0.98,

6 n_shots=2048,

7 histogram=False):

8 phis = get_phases(orig_prob,

9 new_prob)

10

11 @qpu[N,K,D](phis, a, oracle)

12 def amp_iter(phis: angle[2*D],

13 a: rev_qfunc[N],

14 oracle: cfunc[N,1],

15 q: qubit[N+1]) \

16 -> qubit[N+1]:

17 return \

18 q | oracle.xor_embed \

19 | id[N] + \

20 std.rotate(phis[[2*K]]) \

21 | oracle.xor_embed \

22 | ~a + id \

23 | ’0’[N] & std.flip \

24 | id[N] + \

25 std.rotate(phis[[2*K+1]]) \

26 | ’0’[N] & std.flip \

27 | a + id

28

29 @qpu[N,D](phis, a, amp_iter)

30 def kernel(

31 phis: angle[2*D], a: qfunc[N],

32 amp_iter: qfunc[N+1][[...]]) \

33 -> bit[N]:

34 return ’0’[N+1] \

35 | a + id \

36 | (amp_iter[[k]]

37 for k in range(D)) \

38 | std[N].measure + discard

39

40 return kernel(shots=n_shots,

41 histogram=histogram)

Figure 19. Qwerty code for fixed-point amplitude amplification

####  4.3.3. Niroula–Nam substring matching

Niroula and Nam propose a quantum algorithm capable of finding indices of a
substring in $O(\sqrt{N}(\log^{2}N+\log M))$ time (compare with the best known
classical time complexity $\Theta(N+M)$) (Niroula and Nam, 2021). The
algorithm works by preparing a superposition of all possible cyclic bit
rotations of the haystack string and amplifying cases where the needle matches
the beginning of the haystack. Measuring the rotation offset register yields
the indices.

Fig. 20a shows an implementation of substring matching in Qwerty. (It assumes
the length of both the string and pattern are powers of 2.) The K(k) syntax
seen on line 9 is syntactic sugar for explicitly setting a dimension variable
K using a Python int variable named k; this is equivalent to using
[[$\cdots$]] when inference fails, as seen on e.g. line 13 of Fig. 18.

The shift_and_cmp() operation (lines 9-16 of Fig. 20a) is the heart of
Niroula–Nam: taking in the three registers of the algorithm, it cyclically
left-shifts the haystack as mentioned and XORs the beginning of it with the
needle (line 16). If the needle was found, then the last portion of the output
of shift_and_cmp() should be all zeros. This is precisely what the oracle
(lines 31-35 of Fig. 20a) is built to identify.

This example uses fixed-point amplitude amplification (Section 4.3.2) to
amplify the cases where the substring is found (line 37 of Fig. 20a). The
input a, defined on lines 18-29 of Fig. 20a, prepares the state on which to
perform the amplification assuming the input is $\left|00\cdots
0\right\rangle$. The .prep keyword described in Section 3.2.2 is useful here
(lines 26-27) to encode the needle and haystack as qubits. shift_and_cmp() is
then executed in-place (Section 3.2.5). (shift_and_cmp is written a second
time on line 29 because it is its own inverse.)

For convenience, Qwerty allows the operand of .prep (Section 3.2.2) to be a
bit[N], as in pat.prep on line 27 of Fig. 20a. If pat were 1011, for example,
then pat.prep would behave exactly as as ’1011’.prep.

Fig. 20b calls match() (from Fig. 20a) inside typical Python code. Line 7
shows an abbreviated example output given an example input.

⬇

1import math

2from qwerty import *

3from fix_pt_amp import fix_pt_amp

4

5def match(string, pat):

6 n, m = len(string), len(pat)

7 k = math.ceil(math.log2(n))

8

9 @classical[K(k),N(n),M(m)]

10 def shift_and_cmp(off: bit[K],

11 string: bit[N],

12 pat: bit[M]) \

13 -> bit[K+N+M]:

14 return off, \

15 string, \

16 string.rotl(off)[:M] ^ pat

17

18 @qpu[K(k),N,M](string, pat,

19 shift_and_cmp)

20 @reversible

21 def a(string: bit[N], pat: bit[M],

22 shift_and_cmp: cfunc[K+N+M],

23 q: qubit[K+N+M]) \

24 -> qubit[K+N+M]:

25 return \

26 q | ’+’[K].prep + string.prep \

27 + pat.prep \

28 | shift_and_cmp \

29 .inplace(shift_and_cmp)

30

31 @classical[K(k),N(n),M(m)]

32 def oracle(off: bit[K],

33 string: bit[N],

34 pat: bit[M]) -> bit:

35 return (~pat).and_reduce()

36

37 ret = fix_pt_amp(a, oracle, 1/n)

38 return {int(result[:k])

39 for result in set(ret)

40 if oracle(result)}

(a) Qwerty code for Niroula–Nam substring matching

⬇

3import sys

4string = bit.from_str(sys.argv[1])

5pat = bit.from_str(sys.argv[2])

6print(’Matching indices:’)

7for index in match(string, pat):

8 print(index)

9# Output for inputs 1010 and 10: 0, 2

(b) Python for testing Niroula–Nam substring matching

Figure 20. Niroula–Nam substring matching in Qwerty

##  5\. Conclusion

Qwerty is focused on algorithms for quantum information processing as opposed
to quantum physical system modeling (e.g., Hamiltonian simulation) (Manin,
1980; Feynman, 1982). Our goal in creating Qwerty is to help non-experts
reason about quantum computation while abstracting away the complexity of gate
engineering. Qwerty achieves this through abstractions such as qubit literals
based on a string analogy, embedding of classical functions in quantum
kernels, and particularly the basis type. These constructs provide a
programmer with a rich suite of primitives to realize algorithms as code.
Embedding Qwerty in Python achieves both approachability and convenience for
the classical component of quantum–classical programs. This is demonstrated
through Qwerty implementations of significant quantum algorithms such as
Grover’s and Shor’s.

###### Acknowledgements.

The authors thank Elton Pinto and Eugene Dumitrescu for helpful discussions on
quantum programming language design. We acknowledge support for this work from
NSF planning grant #2016666, “Enabling Quantum Computer Science and
Engineering” and through the ORNL STAQCS project. This research was supported
in part through research infrastructure and services provided by the Rogues
Gallery testbed (Young et al., 2019) hosted by the Center for Research into
Novel Computing Hierarchies (CRNCH) at Georgia Tech. The Rogues Gallery
testbed is primarily supported by the National Science Foundation (NSF) under
NSF Award Number #2016701. Any opinions, findings and conclusions, or
recommendations expressed in this material are those of the author(s), and do
not necessarily reflect those of the NSF.

## References

  * (1)
  * Aaronson (2022) Scott Aaronson. 2022\.  _How Much Structure Is Needed for Huge Quantum Speedups?_ Technical Report arXiv:2209.06930. arXiv.  http://arxiv.org/abs/2209.06930 arXiv:2209.06930 [quant-ph].
  * Abhari et al. (2012) Ali Javadi Abhari, Arvin Faruque, Mohammad Javad Dousti, Lukas Svec, Oana Catu, Amlan Chakrabati, Chen-Fu Chiang, Seth Vanderwilt, John Black, Fred Chong, Margaret Martonosi, Martin Suchara, Ken Brown, Massoud Pedram, and Todd Brun. 2012.  _Scaffold: Quantum Programming Language_.  Technical Report. Princeton University Department of Computer Science. 43 pages.
  * Axler (2023) Sheldon Axler. 2023\.  _Linear Algebra Done Right_ (4th ed. 2024 edition ed.).  Springer, Cham, Switzerland.
  * Bennett (1989) Charles H. Bennett. 1989\.  Time/Space Trade-Offs for Reversible Computation.  _SIAM J. Comput._ 18, 4 (Aug. 1989), 766–776.  https://doi.org/10.1137/0218053 Publisher: Society for Industrial and Applied Mathematics.
  * Bernstein and Vazirani (1993) Ethan Bernstein and Umesh Vazirani. 1993.  Quantum complexity theory. In _Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing_ _(STOC ’93)_. Association for Computing Machinery, New York, NY, USA, 11–20.  https://doi.org/10.1145/167088.167097
  * Bichsel et al. (2020) Benjamin Bichsel, Maximilian Baader, Timon Gehr, and Martin Vechev. 2020.  Silq: a high-level quantum language with safe uncomputation and intuitive semantics. In _Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation_ _(PLDI 2020)_. Association for Computing Machinery, New York, NY, USA, 286–300.  https://doi.org/10.1145/3385412.3386007
  * Boyer et al. (1998) Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. 1998.  Tight Bounds on Quantum Searching.  _Fortschritte der Physik_ 46, 4-5 (1998), 493–505.  https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P
  * Brassard (1997) Gilles Brassard. 1997\.  Searching a Quantum Phone Book.  _Science_ 275, 5300 (Jan. 1997), 627–628.  https://doi.org/10.1126/science.275.5300.627 Publisher: American Association for the Advancement of Science.
  * Carette et al. (2023) Jacques Carette, Chris Heunen, Robin Kaarsgaard, and Amr Sabry. 2023.  The Quantum Effect: A Recipe for QuantumPi.  https://doi.org/10.48550/arXiv.2302.01885 arXiv:2302.01885 [quant-ph].
  * Cleve et al. (1998) R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca. 1998\.  Quantum algorithms revisited.  _Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences_ 454, 1969 (Jan. 1998), 339–354.  https://doi.org/10.1098/rspa.1998.0164 Publisher: Royal Society.
  * Cross et al. (2022) Andrew Cross, Ali Javadi-Abhari, Thomas Alexander, Niel De Beaudrap, Lev S. Bishop, Steven Heidel, Colm A. Ryan, Prasahnt Sivarajah, John Smolin, Jay M. Gambetta, and Blake R. Johnson. 2022.  OpenQASM 3: A Broader and Deeper Quantum Assembly Language.  _ACM Transactions on Quantum Computing_ 3, 3 (Sept. 2022), 12:1–12:50.  https://doi.org/10.1145/3505636
  * Deutsch and Jozsa (1997) David Deutsch and Richard Jozsa. 1997.  Rapid solution of problems by quantum computation.  _Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences_ 439, 1907 (Jan. 1997), 553–558.  https://doi.org/10.1098/rspa.1992.0167
  * Deutsch and Penrose (1997) David Deutsch and Roger Penrose. 1997.  Quantum theory, the Church–Turing principle and the universal quantum computer.  _Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences_ 400, 1818 (Jan. 1997), 97–117.  https://doi.org/10.1098/rspa.1985.0070 Publisher: Royal Society.
  * Fallek et al. (2016) S. D. Fallek, C. D. Herold, B. J. McMahon, K. M. Maller, K. R. Brown, and J. M. Amini. 2016\.  Transport implementation of the Bernstein–Vazirani algorithm with ion qubits.  _New Journal of Physics_ 18, 8 (Aug. 2016), 083030.  https://doi.org/10.1088/1367-2630/18/8/083030
  * Feynman (1982) Richard P. Feynman. 1982\.  Simulating physics with computers.  _International Journal of Theoretical Physics_ 21, 6 (June 1982), 467–488.  https://doi.org/10.1007/BF02650179
  * Gilyén et al. (2019) András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. 2019\.  _Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics_.  Technical Report. arXiv. 193–204 pages.  http://arxiv.org/abs/1806.01838 arXiv:1806.01838 [quant-ph].
  * Green et al. (2013) Alexander S. Green, Peter LeFanu Lumsdaine, Neil J. Ross, Peter Selinger, and Benoît Valiron. 2013\.  Quipper: a scalable quantum programming language. In _Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation_ _(PLDI ’13)_. Association for Computing Machinery, New York, NY, USA, 333–342.  https://doi.org/10.1145/2491956.2462177
  * Greenberger et al. (2007) Daniel M. Greenberger, Michael A. Horne, and Anton Zeilinger. 2007\.  Going Beyond Bell’s Theorem.  _arXiv:0712.0921 [quant-ph]_ (Dec. 2007).  http://arxiv.org/abs/0712.0921 arXiv: 0712.0921.
  * Grover (1996) Lov K. Grover. 1996\.  A fast quantum mechanical algorithm for database search. In _Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing_ _(STOC ’96)_. Association for Computing Machinery, New York, NY, USA, 212–219.  https://doi.org/10.1145/237814.237866
  * Grover (1997) Lov K. Grover. 1997\.  Quantum Mechanics Helps in Searching for a Needle in a Haystack.  _Physical Review Letters_ 79, 2 (July 1997), 325–328.  https://doi.org/10.1103/PhysRevLett.79.325 Publisher: American Physical Society.
  * Harris et al. (2020) Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. 2020.  Array programming with NumPy.  _Nature_ 585, 7825 (Sept. 2020), 357–362.  https://doi.org/10.1038/s41586-020-2649-2
  * Li et al. (2022) Liyi Li, Finn Voichick, Kesha Hietala, Yuxiang Peng, Xiaodi Wu, and Michael Hicks. 2022\.  Verified compilation of Quantum oracles.  _Proceedings of the ACM on Programming Languages_ 6, OOPSLA2 (Oct. 2022), 146:589–146:615.  https://doi.org/10.1145/3563309
  * Litteken et al. (2020) Andrew Litteken, Yung-Ching Fan, Devina Singh, Margaret Martonosi, and Frederic T. Chong. 2020.  An updated LLVM-based quantum research compiler with further OpenQASM support.  _Quantum Science and Technology_ 5, 3 (May 2020), 034013.  https://doi.org/10.1088/2058-9565/ab8c2c
  * Lubinski et al. (2022) Thomas Lubinski, Cassandra Granade, Amos Anderson, Alan Geller, Martin Roetteler, Andrei Petrenko, and Bettina Heim. 2022.  Advancing hybrid quantum–classical computation with real-time execution.  _Frontiers in Physics_ 10 (2022), 940293.  https://www.frontiersin.org/articles/10.3389/fphy.2022.940293
  * Manin (1980) Yuri Manin. 1980\.  Computable and uncomputable.  Soviet Radio Publishing House.
  * Martyn et al. (2021) John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. 2021.  Grand Unification of Quantum Algorithms.  _PRX Quantum_ 2, 4 (Dec. 2021), 040203\.  https://doi.org/10.1103/PRXQuantum.2.040203
  * Mccaskey et al. (2021) Alexander Mccaskey, Thien Nguyen, Anthony Santana, Daniel Claudino, Tyler Kharazi, and Hal Finkel. 2021.  Extending C++ for Heterogeneous Quantum-Classical Computing.  _ACM Transactions on Quantum Computing_ 2, 2 (July 2021), 6:1–6:36.  https://doi.org/10.1145/3462670
  * Mintz et al. (2020) Tiffany M. Mintz, Alexander J. McCaskey, Eugene F. Dumitrescu, Shirley V. Moore, Sarah Powers, and Pavel Lougovski. 2020\.  QCOR: A Language Extension Specification for the Heterogeneous Quantum-Classical Model of Computation.  _ACM Journal on Emerging Technologies in Computing Systems_ 16, 2 (March 2020), 22:1–22:17.  https://doi.org/10.1145/3380964
  * Mosca (1999) Michele Mosca. 1999\.  _Quantum Computer Algorithms_.  Ph. D. Dissertation. University of Oxford.
  * Nielsen and Chuang (2010) Michael A. Nielsen and Isaac L. Chuang. 2010.  _Quantum Computation and Quantum Information: 10th Anniversary Edition_ (1st edition ed.).  Cambridge University Press, Cambridge ; New York.
  * Niroula and Nam (2021) Pradeep Niroula and Yunseong Nam. 2021.  A quantum algorithm for string matching.  _npj Quantum Information_ 7, 1 (Feb. 2021), 1–5.  https://doi.org/10.1038/s41534-021-00369-3
  * Núñez-Corrales et al. (2023) Santiago Núñez-Corrales, Marcos Frenkel, and Bruno Abreu. 2023\.  quAPL: Modeling Quantum Computation in an Array Programming Language. In _2023 IEEE International Conference on Quantum Computing and Engineering (QCE)_. IEEE, Bellevue, WA, USA, 1001–1012.  https://doi.org/10.1109/QCE57702.2023.00114
  * Ömer (2000) Bernhard Ömer. 2000\.  _Quantum Programming in QCL_.  Ph. D. Dissertation. Technical University of Vienna.
  * Paradis et al. (2021) Anouk Paradis, Benjamin Bichsel, Samuel Steffen, and Martin Vechev. 2021.  Unqomp: synthesizing uncomputation in Quantum circuits. In _Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation_ _(PLDI 2021)_. Association for Computing Machinery, New York, NY, USA, 222–236.  https://doi.org/10.1145/3453483.3454040
  * Paykin et al. (2017) Jennifer Paykin, Robert Rand, and Steve Zdancewic. 2017\.  QWIRE: a core language for quantum circuits.  _ACM SIGPLAN Notices_ 52, 1 (Jan. 2017), 846–858.  https://doi.org/10.1145/3093333.3009894
  * Paz (2023) Andres Paz. 2023\.  Aleph.  https://github.com/anpaz/aleph
  * Paz et al. (2023) Andres Paz, Cassandra Granade, Mathias Soeken, Guen Prawiroatmodjo, Dmitry Vasilevsky, Alex Hansen, and Cesar Cortes. 2023\.  Sample: Bernstein-Vazirani algorithm.  https://github.com/microsoft/qsharp/blob/5a40497f/samples/algorithms/BernsteinVazirani.qs
  * Pinto (2023) Elton Pinto. 2023\.  Neko: A quantum map-filter-reduce programming language. In _Student Research Competition (SRC)_ _(Symposium on Principles of Programming Languages (POPL’23))_. Boston, MA, USA.  https://www.eltonpinto.me/assets/work/neko-popl23src.pdf
  * Python Software Foundation (2024) Python Software Foundation. 2024\.  fractions — Rational numbers.  https://docs.python.org/3/library/fractions.html
  * Qiskit contributors (2023) Qiskit contributors. 2023\.  Qiskit: An Open-source Framework for Quantum Computing.  https://doi.org/10.5281/zenodo.2573505
  * Rines and Chuang (2018) Rich Rines and Isaac Chuang. 2018.  High Performance Quantum Modular Multipliers.  https://doi.org/10.48550/arXiv.1801.01081 arXiv:1801.01081 [quant-ph].
  * Rosen (2010) Kenneth Rosen. 2010\.  _Elementary Number Theory and Its Application, 6th Edition_ (6th edition ed.).  Pearson.
  * Selinger and Valiron (2006) Peter Selinger and Benoit Valiron. 2006.  A lambda calculus for quantum computation with classical control.  _Mathematical Structures in Computer Science_ 16, 3 (June 2006), 527–552.  https://doi.org/10.1017/S0960129506005238 Publisher: Cambridge University Press.
  * Shor (1994) P.W. Shor. 1994\.  Algorithms for quantum computation: discrete logarithms and factoring. In _Proceedings 35th Annual Symposium on Foundations of Computer Science_. 124–134.  https://doi.org/10.1109/SFCS.1994.365700
  * Shor (1999) Peter W. Shor. 1999\.  Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.  _SIAM Rev._ 41, 2 (Jan. 1999), 303–332.  https://doi.org/10.1137/S0036144598347011 Publisher: Society for Industrial and Applied Mathematics.
  * Shor (2003) Peter W. Shor. 2003\.  Why haven’t more quantum algorithms been found?  _J. ACM_ 50, 1 (Jan. 2003), 87–90.  https://doi.org/10.1145/602382.602408
  * Simon (1994) D.R. Simon. 1994\.  On the power of quantum computation. In _Proceedings 35th Annual Symposium on Foundations of Computer Science_. 116–123.  https://doi.org/10.1109/SFCS.1994.365701
  * Simon (1997) Daniel R. Simon. 1997\.  On the Power of Quantum Computation.  _SIAM J. Comput._ 26, 5 (Oct. 1997), 1474–1483.  https://doi.org/10.1137/S0097539796298637 Publisher: Society for Industrial and Applied Mathematics.
  * Singhal et al. (2022) Kartik Singhal, Kesha Hietala, Sarah Marshall, and Robert Rand. 2022.  Q# as a Quantum Algorithmic Language.  arXiv:2206.03532 [cs.PL]
  * Svore et al. (2018) Krysta Svore, Alan Geller, Matthias Troyer, John Azariah, Christopher Granade, Bettina Heim, Vadym Kliuchnikov, Mariia Mykhailova, Andres Paz, and Martin Roetteler. 2018\.  Q#: Enabling Scalable Quantum Computing and Development with a High-level DSL. In _Proceedings of the Real World Domain Specific Languages Workshop 2018_ _(RWDSL2018)_. Association for Computing Machinery, New York, NY, USA, 1–10.  https://doi.org/10.1145/3183895.3183901
  * Vasilevsky and Cortes (2023) Dmitry Vasilevsky and Cesar Cortes. 2023.  Sample: Grover’s search algorithm.  https://github.com/microsoft/qsharp/blob/d70b544eb78e43c4ec6a88fe8825192930ff47a0/samples/algorithms/Grover.qs
  * Voichick et al. (2023) Finn Voichick, Liyi Li, Robert Rand, and Michael Hicks. 2023\.  Qunity: A Unified Language for Quantum and Classical Computing (Extended Version).  _Proceedings of the ACM on Programming Languages_ 7, POPL (Jan. 2023), 921–951.  https://doi.org/10.1145/3571225 arXiv:2204.12384 [quant-ph].
  * Wadler (1991) Philip Wadler. 1991\.  Is there a use for linear logic?  _ACM SIGPLAN Notices_ 26, 9 (May 1991), 255–273.  https://doi.org/10.1145/115866.115894
  * Watkins (2023) Jacob Watkins. 2023\.  Continued fractions with Shor’s algorithm: which convergent?  Quantum Computing Stack Exchange.  https://quantumcomputing.stackexchange.com/a/32182/
  * Yoder et al. (2014) Theodore J. Yoder, Guang Hao Low, and Isaac L. Chuang. 2014\.  Fixed-Point Quantum Search with an Optimal Number of Queries.  _Physical Review Letters_ 113, 21 (Nov. 2014), 210501.  https://doi.org/10.1103/PhysRevLett.113.210501 Publisher: American Physical Society.
  * Young et al. (2019) Jeffrey S. Young, Jason Riedy, Thomas M. Conte, Vivek Sarkar, Prasanth Chatarasi, and Sriseshan Srikanth. 2019.  Experimental Insights from the Rogues Gallery. In _2019 IEEE International Conference on Rebooting Computing (ICRC)_. 1–8.  https://doi.org/10.1109/ICRC.2019.8914707
  * Yuan and Carbin (2022) Charles Yuan and Michael Carbin. 2022.  Tower: data structures in Quantum superposition.  _Proceedings of the ACM on Programming Languages_ 6, OOPSLA2 (Oct. 2022), 134:259–134:288.  https://doi.org/10.1145/3563297
  * Yuan et al. (2022) Charles Yuan, Christopher McNally, and Michael Carbin. 2022\.  Twist: sound reasoning for purity and entanglement in Quantum programs.  _Proceedings of the ACM on Programming Languages_ 6, POPL (Jan. 2022), 30:1–30:32.  https://doi.org/10.1145/3498691

##  Appendix A Mini-Qwerty Language

In this appendix, we present the soundness of the semantics and type system of
Qwerty. In order to do so, we define Mini-Qwerty, a formalized subset of
Qwerty. We define the core features of the Mini-Qwerty language, including
syntax (Section A.1), typing (Section A.2), semantics (Section A.3), and type
safety (Section A.4). The language formalization below draws from Selinger and
Valiron’s quantum $\lambda$-calculus (Selinger and Valiron, 2006), the $\mu$Q
language due to Yuan et al. (Yuan et al., 2022), and the formalization of Q#
by Singhal et al. (Singhal et al., 2022).

$\textstyle\small\begin{aligned}
&\quad\textit{(Types)}&\>\tau{}{}::={}&\tau_{1}\rightarrow\tau_{2}{}{}\mid{}\tau_{1}\xrightarrow{\text{rev}}\tau_{2}{}{}\mid{}\tau{}_{1}\otimes{}\tau{}_{2}\mid\text{\bf(
)}{}{}\mid{}\mathrm{qubit}{}\mid{}\mathrm{bit}{}{}\mid{}\mathrm{basis}{}\\\
&\quad\textit{(Terms)}&\>t{}{}::={}&e{}\mid b{}\\\
&\quad\textit{(Values)}&\>v{}{}::={}&q_{i}{}\mid x{}\mid 0{}\mid 1{}\mid
bf{}\mid v{}\bm{+}{}v{}\\\
&\quad\textit{(Expressions)}&\>e{}{}::={}&e{}_{1}e{}_{2}{}\mid{}bf{}{}\mid{}x{}{}\mid{}\ell{}{}\mid{}e{}\bm{+}{}e{}{}\mid{}e{}[n]{}{}\mid{}\text{\bf(
)}{}\mid\text{\bf phase}(\theta)*{}e{}\\\ &\quad\textit{(Built-In
Functions)\>}&\>bf{}{}::={}&b{}\text{\bf.measure}{}{}\mid{}b{}_{1}\;\text{>{}>}\;{}b{}_{2}{}\mid{}b{}\;\text{\&}\;{}e{}{}\mid{}{\sim}{}e{}{}\mid{}\text{\bf
id}{}{}\mid{}\text{\bf discard}{}\\\
&\quad\textit{(Literals)}&\>\ell{}{}::={}&0{}\mid{}1{}{}\mid{}q_{i}{}\mid
q\ell{}\\\ &\quad\textit{(Qubit
Literal)}&\>q\ell{}{}::={}&\mathbbm{q}{}[n]{}\\\
&\quad\textit{(Basis)}&\>b{}{}::={}&b_{1}\bm{+}{}b_{2}{}\mid{}b{}[n]{}{}\mid{}\text{\bf
std}{}{}\mid{}\text{\bf pm}{}{}\mid{}\text{\bf ij}{}{}\mid{}\text{\bf
fourier}{}[n]{}{}\mid{}\text{\\{}{}bv{}_{1}\text{\bf,}\>{}bv{}_{2}\text{\bf,}\>{}\cdots\text{\bf,}\>{}bv{}_{m}\text{\\}}{}\\\
&\quad\textit{(Basis Vector)}&\>bv{}{}::={}&q\ell{}{}\mid{}\text{\bf
phase}(\theta)*{}bv{}\end{aligned}$

Figure 21. Mini-Qwerty syntax. Henceforth, $n\geq 0$, $m>0$, and
$\theta\in\mathbb{R}$.

###  A.1. Mini-Qwerty Syntax

Fig. 21 defines Mini-Qwerty types and syntax. (Section A.5 discusses how this
syntax is realized in the Python DSL.) Similar to prior work (Paykin et al.,
2017; Yuan et al., 2022), Mini-Qwerty has both linear types and nonlinear
types. In particular, functions and classical types (namely the $\mathrm{bit}$
type) are nonlinear, but any type holding a qubit (i.e., a qubit or a tuple
including qubits) is linear.

In Mini-Qwerty, the tensor product is associative for both terms and types;
for example, the type
$\mathrm{qubit}\otimes{}(\mathrm{qubit}\otimes\mathrm{qubit})$ is identical to
the type $(\mathrm{qubit}\otimes{}\mathrm{qubit})\otimes\mathrm{qubit}$, and
the term $t_{1}\bm{+}{}(t_{2}\bm{+}{}t_{3})$ is exactly the term
$(t_{1}\bm{+}{}t_{2})\bm{+}{}t_{3}$. We show later that this facilitates
taking the tensor product of functions, a major Qwerty idiom. We denote ( ) as
an empty tensor product for both expressions and types. For a type $\tau$, we
write $\tau[n]{}$ as shorthand for an $n$-fold tensor product of $\tau$, i.e.,
$\bigotimes_{i=1}^{n}\tau{}$.

For simplicity, we assume a Mini-Qwerty program is an expression, although
Mini-Qwerty can be easily extended to represent a program with multiple
functions and embeddings of classical functions (Section 3.2.5). The
expressions are built on typical expressions like applications and variables
alongside specific quantum expressions like bases and built-in functions. Our
built-in functions are either categorized as reversible or not, where
reversible generally means no qubits are measured or discarded555For
simplicity, Mini-Qwerty also requires that reversible functions return all
input qubits in exactly the same order they were passed.. The reversible
distinction for functions (called “adjointable” by Singhal et al. (Singhal et
al., 2022)) is important for the Mini-Qwerty & and ${\sim}{}$ operators (the
predicator and reverser, respectively), which can only act on reversible
functions; we elaborate in Section A.3.

Bit literals are 0 and 1 as usual. id is the single-qubit identity function
and is useful for padding functions out to apply to more qubits. The syntax ¿¿
performs the crucial basis translation introduced in Section 3.2.2. (We
describe bases in more detail in the next section.) The operator $\text{\bf
phase}(\theta){*}{}$ imparts a phase $e^{i\theta}$ on qubits or basis vectors.

Although qubit literals are written as string literals in the Python DSL per
Section 3.2.1, we avoid overspecializing for Python and permit a more abstract
form $\mathbbm{q}{}$ of qubit literals in Mini-Qwerty. We assume each
$\mathbbm{q}$ is a nonempty sequence of the symbols 0, 1, +, -, i, and j. The
notation $|\mathbbm{q}{}|$ denotes the length of this sequence.
$\left|\mathbbm{q}\right\rangle$ denotes the quantum state that
$\mathbbm{q}{}$ represents — for example, if $\mathbbm{q}{}={}$+10-, then
$\left|\mathbbm{q}{}\right\rangle=\left|+\right\rangle\otimes\left|10\right\rangle\otimes\left|-\right\rangle$.
The $[n]{}$ suffix following $\mathbbm{q}{}$ prepares $n$ duplicate versions
of $\mathbbm{q}$.

Finally, $q_{i}$, which represents a reference to the qubit at index $i$, is
not written by programmers; it is used only during evaluation (Yuan et al.,
2022).

$\textstyle\small\begin{gathered}x{}:{}\tau{}\vdash_{\varnothing}x{}:{}\tau{}\quad{}\cdot{}\vdash_{\varnothing}0{}:{}\mathrm{bit}{}\quad{}\cdot{}\vdash_{\varnothing}1{}:{}\mathrm{bit}{}\quad{}\cdot{}\vdash_{\varnothing}\mathbbm{q}{}[m]{}:{}\mathrm{qubit}{}[m|\mathbbm{q}{}|]{}\\\\[2.25pt]
{}\cdot{}\vdash_{\\{i\\}}q_{i}{}:{}\mathrm{qubit}\quad{}\Gamma{}\vdash_{\varnothing}\text{\bf(
)}{}:{}\text{\bf( )}{}\quad{}\cdot{}\vdash_{\varnothing}\text{\bf
std}{}:{}\mathrm{basis}{}\quad{}\cdot{}\vdash_{\varnothing}\text{\bf
pm}{}:{}\mathrm{basis}{}\quad{}\cdot{}\vdash_{\varnothing}\text{\bf
ij}{}:{}\mathrm{basis}{}\\\\[2.25pt] {}\cdot{}\vdash_{\varnothing}\text{\bf
fourier}{}[n]{}:{}\mathrm{basis}{}[n]{}\quad{}\cdot{}\vdash_{\varnothing}\text{\bf
id}{}:{}\mathrm{qubit}{}\xrightarrow{\text{rev}}{}\mathrm{qubit}{}\quad{}\cdot{}\vdash_{\varnothing}\text{\bf
discard}{}:{}\mathrm{qubit}{}\rightarrow{}\text{\bf( )}{}\\\\[2.25pt]
{}\Gamma{}_{1},\Gamma{}_{2},\cdots,\Gamma{}_{m_{2}}\vdash_{\varnothing}\text{\\{}{}bv{}_{1}\text{\bf,}\>{}\cdots\text{\bf,}\>{}bv{}_{m_{2}}\text{\\}}{}:{}\mathrm{basis}{}[m_{1}]{}\begin{gathered}\Gamma{}_{1}\vdash_{\Delta_{1}}bv{}_{1}:{}\mathrm{qubit}{}[m_{1}]{}\quad{}\Gamma{}_{2}\vdash_{\Delta_{2}}bv{}_{2}:{}\mathrm{qubit}{}[m_{1}]{}\;\;\cdots\;\;{}\Gamma{}_{m}\vdash_{\Delta_{m_{2}}}bv{}_{m_{2}}:{}\mathrm{qubit}{}[m_{1}]{}\\\\[-2.25pt]
{}\forall_{i=1}^{m_{2}}\
|{}bv{}_{i}|{}=m_{1}\quad{}\exists_{\sigma\in\\{\sigma_{x},\sigma_{y},\sigma_{z}\\}}\forall_{i=1}^{m_{2}}\
\sigma^{\otimes
n}\left|bv{}_{i}\right\rangle=\lambda_{i}\left|bv{}_{i}\right\rangle\quad{}\forall_{i\neq
j=1}^{m_{2}}\ \forall\theta\in\mathbb{R},\
e^{i\theta}\left|bv{}_{i}\right\rangle\neq\left|bv{}_{j}\right\rangle\end{gathered}\end{gathered}$

Figure 22. Mini-Qwerty type rules for values and bases

$\textstyle\small\begin{gathered}\Gamma{}_{1},\Gamma{}_{2}\vdash_{\Delta_{1}\sqcup\Delta_{2}}t{}_{1}\bm{+}{}t{}_{2}:{}\tau{}_{1}\otimes{}\tau{}_{2}\Gamma{}_{1}\vdash_{\Delta_{1}}t{}_{1}:{}\tau{}_{1}\quad{}\Gamma{}_{2}\vdash_{\Delta_{2}}t{}_{2}:{}\tau{}_{2}\quad{}\Gamma{}\vdash_{\varnothing}t{}[n_{2}]{}:{}\tau{}[n_{2}]{}\Gamma{}\vdash_{\varnothing}t{}:{}\tau{}\quad{}\tau\neq\tau_{1}\otimes{}\mathrm{qubit}{}\otimes{}\tau_{2}\\\\[2.25pt]
{}\Gamma{}\vdash_{\Delta}\text{\bf
phase}(\theta)*{}e{}:{}\mathrm{qubit}[m]{}\Gamma{}\vdash_{\Delta}e{}:{}\mathrm{qubit}[m]{}\quad{}\Gamma{}_{1},\Gamma{}_{2}\vdash_{\Delta_{1}\sqcup\Delta_{2}}e{}_{1}e{}_{2}:{}\tau{}_{2}\Gamma{}_{1}\vdash_{\Delta_{1}}e{}_{1}:{}\tau{}_{1}\rightarrow{}\tau{}_{2}\quad{}\Gamma{}_{2}\vdash_{\Delta_{2}}e{}_{2}:{}\tau{}_{1}\\\\[2.25pt]
{}\Gamma{}\vdash_{\varnothing}b{}\text{\bf.measure}{}:{}\mathrm{qubit}{}[m]{}\rightarrow{}\mathrm{bit}{}[m]{}\Gamma{}\vdash_{\varnothing}b{}:\mathrm{basis}{}[m]{}\quad{}\mathrm{span}(b{})=\mathcal{H}_{2}{}^{\otimes
m}\quad{}\Gamma{}_{1},\Gamma{}_{2}\vdash_{\varnothing}b{}_{1}\;\text{>{}>}\;{}b{}_{2}:\mathrm{qubit}{}[m]{}\xrightarrow{\text{rev}}{}\mathrm{qubit}{}[m]{}\begin{gathered}\Gamma{}_{1}\vdash_{\varnothing}b{}_{1}:\mathrm{basis}{}[m]{}\quad{}\Gamma{}_{2}\vdash_{\varnothing}b{}_{2}:\mathrm{basis}{}[m]{}\\\\[-2.25pt]
{}\mathrm{span}(b{}_{1})=\mathrm{span}(b{}_{2})\end{gathered}\\\\[2.25pt]
{}\Gamma{}_{1},\Gamma{}_{2}\vdash_{\Delta}b{}\;\text{\&}\;{}e{}:{}\mathrm{qubit}{}[m_{1}+m_{2}]{}\xrightarrow{\text{rev}}{}\mathrm{qubit}{}[m_{1}+m_{2}]{}\Gamma{}_{1}\vdash_{\varnothing}b{}:{}\mathrm{basis}{}[m_{1}]{}\quad{}\Gamma{}_{2}\vdash_{\Delta}e{}:{}\mathrm{qubit}{}[m_{2}]{}\xrightarrow{\text{rev}}{}\mathrm{qubit}{}[m_{2}]{}\quad{}\Gamma{}\vdash_{\Delta}{\sim}{}e{}:{}\mathrm{qubit}{}[m]{}\xrightarrow{\text{rev}}{}\mathrm{qubit}{}[m]{}\Gamma{}\vdash_{\Delta}e{}:{}\mathrm{qubit}{}[m]{}\xrightarrow{\text{rev}}{}\mathrm{qubit}{}[m]{}\end{gathered}$

Figure 23. Mini-Qwerty type rules for operations

$\textstyle\small\begin{gathered}\Gamma{}\vdash_{\Delta}e{}:{}\tau_{2}\tau_{1}<:{}\tau_{2}\quad{}\Gamma{}\vdash_{\Delta}e{}:{}\tau_{1}\quad{}\tau_{1}\xrightarrow{\text{rev}}{}\tau_{2}<:{}\tau_{1}\rightarrow{}\tau_{2}\\\\[2.25pt]
{}\begin{gathered}\textstyle\left((\bigotimes_{i=1}^{n_{1}}\tau_{i})\rightarrow{}(\bigotimes_{j=1}^{n_{2}}\tau_{j})\right)\otimes{}\left((\bigotimes_{k=1}^{n_{3}}\tau_{k})\rightarrow{}(\bigotimes_{\ell=1}^{n_{4}}\tau_{\ell})\right)\\\
\textstyle<:{}\left((\bigotimes_{i=1}^{n_{1}}\tau_{i})\otimes{}(\bigotimes_{k=1}^{n_{3}}\tau_{k})\right)\rightarrow{}\left((\bigotimes_{j=1}^{n_{2}}\tau_{j})\otimes{}(\bigotimes_{\ell=1}^{n_{4}}\tau_{\ell})\right)\end{gathered}\end{gathered}$

Figure 24. Mini-Qwerty subtyping rules

###  A.2. Mini-Qwerty Type System

Fig. 22 and Fig. 23 show the typing rules for Mini-Qwerty. In our typing
rules, a term ($\bm{t{}}$) with type ($\bm{\tau{}}$) based on context
($\bm{\Gamma}$) and qubit index context ($\bm{\Delta}$) is well-typed in the
given judgement: $\Gamma{}\vdash_{\Delta}t{}:{}\tau{}$. The qubit index
context $\Delta$ is a set of positive integers representing the set of all
qubit indices $i$ in all $q_{i}$ values in the expression. We write $A\sqcup
B$ to denote the union of disjoint sets $A$ and $B$, and $[n]$ is defined as
the set $\\{1,2,\ldots,n\\}$. When the type is linear ($\mathrm{qubit}$s, or
tensor product holding $\mathrm{qubit}$s), we only allow exchange rules on the
context $\Gamma$ to maintain linearity (Wadler, 1991; Selinger and Valiron,
2006; Paykin et al., 2017; Yuan et al., 2022). In the other cases (for non-
quantum types), we also allow weakening and contraction.

Fig. 24 defines the subtyping rules for Mini-Qwerty. Srev exists for
programmer convenience, since a reversible function should be usable anywhere
an ordinary irreversible function could be. The StensFunc rule facilitates a
unique feature of Qwerty: the ability to use the tensor product of functions
(i.e., tuples of functions) in an application. For example, applying
$(\text{\bf id}{}\bm{+}{}\text{\bf discard}{}\bm{+}{}\text{\bf id}{})$ to
three qubits would preserve the leftmost and rightmost qubits, but discard the
middle qubit.

The rule Tbasis mandates that a basis literal
$\text{\\{}{}bv{}_{1}\text{\bf,}\>{}bv{}_{2}\text{\bf,}\>{}\cdots\text{\bf,}\>{}bv{}_{m}\text{\\}}{}$
meets all the following conditions, which guarantee that it satisfies the
linear algebraic definition of an orthonormal basis (Axler, 2023):

  1. (1)

All $bv{}_{i}$ must have the same number of qubits (denoted $|bv{}_{i}|$).

  2. (2)

No $bv{}_{i}$s are expressed as a mixture of symbols from the pairs 0/1, +/-,
and i/j. In mathematical terms, either all $\left|bv{}_{i}\right\rangle$ are
eigenstates of $\sigma_{x}^{\otimes|bv{}_{1}|}$, or all are eigenstates of
$\sigma_{y}^{\otimes|bv{}_{1}|}$ instead, or all are eigenstates of
$\sigma_{z}^{\otimes|bv{}_{1}|}$ instead. This helps ensure all $q_{i}$s are
linearly independent; for example, the list of vectors
$\left|0\right\rangle,\left|1\right\rangle,\left|+\right\rangle$ is linearly
dependent.

  3. (3)

$bv{}_{i}$s cannot be repeated, even with a different phase. Mathematically,
for any $1\leq i,j\leq m$ such that $i\neq j$, there exists no
$\theta\in\mathbb{R}$ such that
$e^{i\theta}\left|bv{}_{i}\right\rangle=\left|bv{}_{j}\right\rangle$. This
also helps guarantee linear independence.

$\textstyle\small\begin{aligned}
\left(\left|\psi_{i}\right\rangle\right)_{i=1}^{n_{1}}\otimes\left(\left|\phi_{j}\right\rangle\right)_{j=1}^{n_{2}}&\triangleq\left(\left|\psi_{i}\right\rangle\otimes\left|\phi_{j}\right\rangle\right)_{i=1,2,\ldots,n_{1};\>j=1,2,\ldots,n_{2}}\\\
\mathrm{veclist}(b{}_{1}\bm{+}{}b{}_{2})&\triangleq\mathrm{veclist}(b{}_{1})\otimes\mathrm{veclist}(b{}_{2})\\\
\mathrm{veclist}(b{}[n]{})&\triangleq\mathrm{veclist}(\textstyle\operatorname*{\scalerel*{{+}}{\sum}}{}_{i=1}^{n}b{})\\\
\mathrm{veclist}(\text{\bf
std}{})&\triangleq\left|0\right\rangle,\left|1\right\rangle\\\
\mathrm{veclist}(\text{\bf
pm}{})&\triangleq\left|+\right\rangle,\left|-\right\rangle\\\
\mathrm{veclist}(\text{\bf
ij}{})&\triangleq\left|+i\right\rangle,\left|-i\right\rangle\\\
\mathrm{veclist}(\text{\bf
fourier}{}[n]{})&\triangleq\left|F_{0}\right\rangle,\left|F_{1}\right\rangle,\ldots,\left|F_{2^{n}-1}\right\rangle\\\
&\quad\>\text{with
}\left|F_{j}\right\rangle\triangleq\frac{1}{\sqrt{2^{n}}}\textstyle\sum^{2^{n}-1}_{k=0}e^{i2\pi
jk/2^{n}}\left|k\right\rangle\\\ \mathrm{vec}(\text{\bf
phase}(\theta)*{}bv{})&\triangleq e^{i\theta}\mathrm{vec}(bv{})\\\
\mathrm{vec}(\mathbbm{q}{}[n]{})&\triangleq\textstyle\bigotimes_{i=1}^{n}\left|\mathbbm{q}{}\right\rangle\\\
\mathrm{veclist}(\text{\\{}{}bv{}_{1}\text{\bf,}\>{}bv{}_{2}\text{\bf,}\>{}\ldots\text{\bf,}\>{}bv{}_{m}\text{\\}}{})&\triangleq\mathrm{vec}(bv{}_{1}),\mathrm{vec}(bv{}_{2}),\ldots,\mathrm{vec}(bv{}_{m})\\\
\left|b{}^{1}\right\rangle,\left|b{}^{2}\right\rangle,\ldots,\left|b{}^{m}\right\rangle&\triangleq\mathrm{veclist}(b{})\\\
\mathrm{span}(b{})&\triangleq\mathrm{span}\left(\left|b{}^{1}\right\rangle,\left|b{}^{2}\right\rangle,\ldots,\left|b{}^{m}\right\rangle\right)\\\
|b{}|&\triangleq m\text{ for which
}\left|b{}^{1}\right\rangle\in\mathcal{H}_{2}{}^{\otimes m}\end{aligned}$

Figure 25. Definition of properties of a basis $b{}$, including the number of
qubits across which it is defined (written $|b|$) and the list of vectors it
represents. This list is an orthonormal basis if $b{}$ is well-typed. The
notation $(\cdot)_{i=1}^{n}$ denotes a comma-separated list of length $n$.

$\textstyle\small\begin{gathered}[\left|\psi\right\rangle,\text{\bf
id}{}\>q_{i}{}]\longrightarrow{}[\left|\psi\right\rangle,q_{i}{}]\quad{}[\left|\psi\right\rangle,\text{\bf
discard}{}\>q_{i}{}]\longrightarrow{}[\left|\psi\right\rangle,\text{\bf(
)}{}]\\\\[2.25pt]
{}[\left|\psi\right\rangle,\mathbbm{q}{}[m]{}]\longrightarrow{}[\left|\psi\right\rangle\otimes\bigotimes_{i=1}^{m}\left|\mathbbm{q}{}\right\rangle,\operatorname*{\scalerel*{{+}}{\sum}}_{j=1}^{m|\mathbbm{q}|}q_{i_{j}}]\\\\[2.25pt]
{}[\left|\psi\right\rangle,(b{}_{1}\;\text{>{}>}\;{}b{}_{2})(\operatorname*{\scalerel*{{+}}{\sum}}^{m}_{j=1}q_{i_{j}})]\longrightarrow{}[U_{b{}_{1}\rightarrow
b{}_{2}}^{\vec{i}}\left|\psi\right\rangle,\operatorname*{\scalerel*{{+}}{\sum}}^{m}_{j=1}q_{i_{j}}]|b_{1}|=|b_{2}|=m\\\\[2.25pt]
{}[\left|\psi\right\rangle,b{}\text{\bf.measure}{}(\operatorname*{\scalerel*{{+}}{\sum}}^{m}_{j=1}q_{i_{j}})]\xlongrightarrow{p^{\vec{i}}_{b,j}\left(\left|\psi\right\rangle\right)}[\frac{M_{b{},j}^{\vec{i}}}{\sqrt{p^{\vec{i}}_{b,j}\left(\left|\psi\right\rangle\right)}}\left|\psi\right\rangle,\mathbb{B}_{m,j}^{m-1}\bm{+}{}\mathbb{B}_{m,j}^{m-2}\bm{+}{}\cdots\bm{+}{}\mathbb{B}_{m,j}^{0}]|b{}|=m\\\\[2.25pt]
{}[\left|\psi\right\rangle,e{}[n]{}]\longrightarrow{}[\left|\psi\right\rangle,\operatorname*{\scalerel*{{+}}{\sum}}_{j=1}^{n}e]\quad{}[\left|\psi\right\rangle,\text{\bf
phase}(\theta)*{}e{}]\longrightarrow{}[\left|\psi^{\prime}\right\rangle,\text{\bf
phase}(\theta)*{}e{}^{\prime}][\left|\psi\right\rangle,e{}]\longrightarrow{}[\left|\psi^{\prime}\right\rangle,e{}^{\prime}]\\\\[2.25pt]
{}[\left|\psi\right\rangle,\text{\bf
phase}(\theta)*{}(\operatorname*{\scalerel*{{+}}{\sum}}^{m}_{j=1}q_{i_{j}})]\longrightarrow{}[e^{i\theta}\left|\psi\right\rangle,\operatorname*{\scalerel*{{+}}{\sum}}^{m}_{j=1}q_{i_{j}}]\\\\[2.25pt]
{}[\left|\psi\right\rangle,({\sim}{}e{})(\operatorname*{\scalerel*{{+}}{\sum}}_{j=1}^{m}q_{i_{j}})]\longrightarrow{}[(U^{\vec{i}})^{\dagger}\left|\psi\right\rangle,\operatorname*{\scalerel*{{+}}{\sum}}_{j=1}^{m}q_{i_{j}}][\left|\psi^{\prime}\right\rangle,e{}(\operatorname*{\scalerel*{{+}}{\sum}}_{j=1}^{m}q_{i_{j}})]\longrightarrow{}[U^{\vec{i}}\left|\psi^{\prime}\right\rangle,\operatorname*{\scalerel*{{+}}{\sum}}_{j=1}^{m}q_{i_{j}}]\quad{}\left|\psi\right\rangle,\left|\psi^{\prime}\right\rangle\in\mathcal{H}_{2}{}^{\otimes
n}\\\\[2.25pt]
{}[\left|\psi\right\rangle,(b{}\;\text{\&}\;{}e{})((\operatorname*{\scalerel*{{+}}{\sum}}_{k=1}^{m_{2}}q_{i_{k}^{p}})\bm{+}{}(\operatorname*{\scalerel*{{+}}{\sum}}_{j=1}^{m_{1}}q_{i_{j}}))]\longrightarrow{}[C_{b{}}U^{\vec{i}^{p},\vec{i}}\left|\psi\right\rangle,(\operatorname*{\scalerel*{{+}}{\sum}}_{k=1}^{m_{2}}q_{i_{k}^{p}})\bm{+}{}(\operatorname*{\scalerel*{{+}}{\sum}}_{j=1}^{m_{1}}q_{i_{j}})]|b{}|=m_{2}\quad{}[\left|\psi^{\prime}\right\rangle,e{}(\operatorname*{\scalerel*{{+}}{\sum}}_{j=1}^{m_{1}}q_{i_{j}})]\longrightarrow{}[U^{\vec{i}}\left|\psi^{\prime}\right\rangle,\operatorname*{\scalerel*{{+}}{\sum}}_{j=1}^{m_{1}}q_{i_{j}}]\quad{}\left|\psi\right\rangle,\left|\psi^{\prime}\right\rangle\in\mathcal{H}_{2}{}^{\otimes
n}\\\\[2.25pt]
{}[\left|\psi\right\rangle,(\operatorname*{\scalerel*{{+}}{\sum}}_{j=1}^{n_{1}}v_{j})\bm{+}{}e{}_{1}\bm{+}{}(\operatorname*{\scalerel*{{+}}{\sum}}_{k=2}^{n_{2}}e{}_{k})]\longrightarrow{}[\left|\psi^{\prime}\right\rangle,(\operatorname*{\scalerel*{{+}}{\sum}}_{j=1}^{n_{1}}v_{j})\bm{+}{}e{}_{1}^{\prime}\bm{+}{}(\operatorname*{\scalerel*{{+}}{\sum}}_{k=2}^{n_{2}}e{}_{k})][\left|\psi\right\rangle,e{}_{1}]\longrightarrow{}[\left|\psi^{\prime}\right\rangle,e{}_{1}^{\prime}]\quad{}n_{1}+n_{2}>0\\\\[2.25pt]
{}[\left|\psi\right\rangle,(\operatorname*{\scalerel*{{+}}{\sum}}^{m}_{k=1}v{}_{k})(\operatorname*{\scalerel*{{+}}{\sum}}^{n_{2}}_{j=1}v{}_{j}^{\prime})]\longrightarrow{}[\left|\psi^{\prime}\right\rangle,e{}\bm{+}{}((\operatorname*{\scalerel*{{+}}{\sum}}^{m}_{k=2}v{}_{k})(\operatorname*{\scalerel*{{+}}{\sum}}^{n_{2}}_{j=n_{1}+1}v{}_{j}^{\prime}))][\left|\psi\right\rangle,v{}_{1}(\operatorname*{\scalerel*{{+}}{\sum}}_{j=1}^{n_{1}}v{}_{j}^{\prime})]\longrightarrow{}[\left|\psi^{\prime}\right\rangle,e{}]\quad{}n_{1}\leq
n_{2}\\\\[2.25pt]
{}[\left|\psi\right\rangle,e{}_{1}\>e{}_{2}]\xlongrightarrow{p}[\left|\psi^{\prime}\right\rangle,e{}_{1}^{\prime}\>e{}_{2}][\left|\psi\right\rangle,e{}_{1}]\xlongrightarrow{p}[\left|\psi^{\prime}\right\rangle,e{}_{1}^{\prime}]\quad{}[\left|\psi\right\rangle,v{}\>e{}]\xlongrightarrow{p}[\left|\psi^{\prime}\right\rangle,v{}\>e{}^{\prime}][\left|\psi\right\rangle,e{}]\xlongrightarrow{p}[\left|\psi^{\prime}\right\rangle,e{}^{\prime}]\end{gathered}$

Figure 26. Mini-Qwerty evaluation rules

The Tmeasure rule requires that the operand $b{}$ of $b{}\text{\bf.measure}{}$
is a basis for the full $n$-qubit Hilbert space ($\mathcal{H}_{2}{}^{\otimes
n}$). The judgment of $b{}$ as well-typed ensures that $b{}$ is an orthonormal
list; if this orthonormal list spans $\mathcal{H}_{2}{}^{\otimes n}$, then
$b{}$ represents an $n$-qubit basis, meaning the resulting measurement
operators (Section A.3) satisfy the completeness equation (Nielsen and Chuang,
2010, §2.2.3). A basis translation $b{}_{1}\;\text{>{}>}\;{}b{}_{2}$, on the
other hand, mandates that $b{}_{1}$ and $b{}_{2}$ span the same spaces
(Tbtrans), preserving unitarity. (Fig. 25 formally defines the span of a basis
$b{}$.)

The predicator operator $b{}\;\text{\&}\;e{}$ returns a new function which
runs the function $e{}$ only in the subspace $b{}$. Here, $e{}$ must be a
reversible function — specifically, this means it must have the effect of a
unitary on the state, meaning it cannot perform measurements or discard qubits
(Singhal et al., 2022).

###  A.3. Mini-Qwerty Semantics

Fig. 26 shows the evaluation rules for Mini-Qwerty. Because classical control
hardware executes a Mini-Qwerty program, causing side effects on a quantum
state, we represent the state of a Mini-Qwerty program as a pair
$[\left|\psi\right\rangle,e{}]$ of a quantum state $\left|\psi\right\rangle$
and a Mini-Qwerty expression $e{}$ (Selinger and Valiron, 2006; Yuan and
Carbin, 2022). The initial quantum state may be chosen as
$\left|\right\rangle=\begin{bmatrix}1\end{bmatrix}$, a $1{\times}1$ matrix.
(For notational convenience, we denote $\mathrm{span}(\left|\right\rangle)$ as
$\mathcal{H}_{2}{}^{\otimes 0}$.)

The evaluation relation
$[\left|\psi\right\rangle,e{}]\xlongrightarrow{p}[\left|\psi^{\prime}\right\rangle,e^{\prime}]$
includes a probability $p$ to account for quantum nondeterminism (Selinger and
Valiron, 2006; Yuan and Carbin, 2022). Often $p$ is omitted, as in
$[\left|\psi\right\rangle,e{}]\longrightarrow{}[\left|\psi^{\prime}\right\rangle,e^{\prime}]$,
which should be read as letting $p=1$. Currently, due to the possibility of
different measurement results, only Emeasure introduces a probability $p$
which may not be equal to $1$.

The rule Ediscard permits the programmer to explicitly discard a qubit
reference $q_{i}$. The hardware or runtime may reset $q_{i}$ to
$\left|0\right\rangle$ for later use, but Mini-Qwerty does not implement this
for simplicity. Conversely, rule Eqlit prepares $n$ copies of the requested
state $\left|\mathbbm{q}{}\right\rangle$; a runtime may repurpose previously
discarded qubits, but for notational simplicity we simply expand
$\left|\psi\right\rangle$ to include the new qubits. If
$\left|\psi\right\rangle\in\mathcal{H}_{2}{}^{\otimes n}$, then the indices
$i_{j}$ in Eqlit are defined as $i_{j}\triangleq n+j$ to ensure the new
$q_{i_{j}}$ point to the fresh qubits.

Ebtrans describes the behavior of basis translations, introduced in Section
3.2.2. (In all rules, the notation $U^{i_{1},i_{2},\ldots,i_{n}}$, abbreviated
as $U^{\vec{i}}$, means $U$ should be applied to the qubits at indices
$i_{1},i_{2},\ldots,i_{n}$.) In essence, $U_{b_{1}\rightarrow b_{2}}$ is
$\mathrm{diag}(1,1,\ldots,1)$ where the columns are written in the basis
$b_{1}$, and the rows are written in the basis $b_{2}$. To define this more
rigorously, first suppose $\mathrm{span}(b_{1})=\mathrm{span}(b_{2})$ (defined
in Fig. 25) and the vectors of the bases they represent are
$\left|b_{i}^{k}\right\rangle$, $i\in\\{1,2\\}$ (defined formally in Fig 25).
If $\left|b_{1}^{k}\right\rangle$ is extended to an orthonormal basis
$\left|e_{1}^{k}\right\rangle$ of $\mathcal{H}_{2}{}^{\otimes n}$ with
Gram–Schmidt (Axler, 2023; Nielsen and Chuang, 2010), then let
$\left|e_{2}^{k}\right\rangle$ be $\left|b_{2}^{k}\right\rangle$ extended with
the same vectors by which $\left|b_{1}^{k}\right\rangle$ was extended. Then we
define $U_{b_{1}\rightarrow
b_{2}}=\sum_{k}\left|e_{2}^{k}\right\rangle\left\langle e_{1}^{k}\right|$.

Measurement, defined by Emeasure, also takes a basis operand. If $|b{}|=m$,
then measurement operators
$M_{b{},i}\triangleq\left|b^{i}\right\rangle\\!\left\langle b^{i}\right|$ are
projectors onto the $2^{m}$ basis states of $b{}$. The notation
$p^{\vec{i}}_{b{},j}\left(\left|\psi\right\rangle\right)=\langle\psi|M^{\vec{i}}_{b{},j}|\psi\rangle$
describes the probability of observing outcome $1\leq j\leq 2^{m}$ on the
qubits at indices $\vec{i}$ of $\left|\psi\right\rangle$. We represent the
measurement outcome itself as $m$-bit binary: $\mathbb{B}_{m,j}$ is $j{-}1$
expressed in $m$-bit binary, and $\mathbb{B}_{m,j}^{k}$ is bit $k$, where
$\mathbb{B}_{m,j}^{0}$ is the least significant.

Epred defines the behavior of the predicator (&), which predicates a function
running on a set of qubits ($q_{i_{j}}$) on a subspace of predicate qubits
($q_{i_{k}^{p}}$). Here we describe the $C_{b}U$ notation used in the rule.
Using Gram–Schmidt, extend $\left|b{}^{k}\right\rangle$, the basis represented
by $b{}$, to an orthonormal basis of $\mathcal{H}_{2}{}^{\otimes n_{2}}$,
denoting vectors by which $\left|b{}^{k}\right\rangle$ would be extended as
$\left|e^{\ell}\right\rangle$ (Axler, 2023; Nielsen and Chuang, 2010). Then if
$U$ is an $n$-qubit unitary, let
$C_{b{}}U=\left(\sum_{\ell}\left|e^{\ell}\right\rangle\left\langle
e^{\ell}\right|\right)\otimes
I_{2^{n}}+\left(\sum_{k}\left|b{}^{k}\right\rangle\left\langle
b{}^{k}\right|\right)\otimes U$.

Besides the aforementioned basis-oriented quantum primitives, EtensApp defines
how exactly tensor products of functions are applied in Mini-Qwerty. The
functions in the tensor product are evaluated left-to-right. The number of
values to peel off and pass to the leftmost function ($n_{1}$ in EtensApp) is
determined based on the prototype of the function, which must specify the
number of inputs; for example, extending Fig. 21 to include lambdas would
require an annotation to specify the number of input values, like
$\lambda(x{}_{1}{:{}}\tau{}_{1},x{}_{2}{:{}}\tau{}_{1},\ldots,x{}_{n}{:{}}\tau{}_{n}).e{}$.

###  A.4. Mini-Qwerty Properties

As with any new language, we need to prove progress and preservation. These
properties prove the type safety of Mini-Qwerty. Progress states a type-safe
expression means it is either a value or can do one step of evaluation.
Preservation states a type-safe expression with an evaluation step to a new
expression should be type-safe. We state the mathematical formulas as Theorem
A.1 and Theorem A.2 respectively.

###### Theorem A.1.

(Progress) If $\cdot\vdash_{\Delta}e{}:{}\tau{}$, either e is a value or
$\forall\left|\psi\right\rangle\in\mathcal{H}_{2}{}^{\otimes n}$ where
$\Delta\subseteq[n]$,
$[\left|\psi\right\rangle,e{}]\xlongrightarrow{p}[\left|\psi^{\prime}\right\rangle,e{}^{\prime}]$.

###### Theorem A.2.

(Preservation) If $\Gamma{}\vdash_{n}e{}:{}\tau{}$ and
$[\left|\psi\right\rangle,e{}]\xlongrightarrow{p}[\left|\psi^{\prime}\right\rangle,e{}^{\prime}]$
and $\left|\psi\right\rangle\in\mathcal{H}_{2}{}^{\otimes n}$ with
$\Delta\subseteq[n]$, then
$\Gamma{}\vdash_{\Delta^{\prime}}e{}^{\prime}:{}\tau{}$ and
$\left|\psi^{\prime}\right\rangle\in\mathcal{H}_{2}{}^{\otimes n^{\prime}}$
where $\Delta^{\prime}\subseteq[n^{\prime}]$.

Progress can be proved by induction on derivation of
$\cdot\vdash_{\Delta}e{}:{}\tau{}$. Preservation is an induction on derivation
of
$[\left|\psi\right\rangle,e{}]\xlongrightarrow{p}[\left|\psi^{\prime}\right\rangle,e{}^{\prime}]$
(Yuan et al., 2022).

###### Theorem A.3.

(Universality) Mini-Qwerty is universal.

###### Proof.

The following basis translation performs a unitary transformation exactly
equal to an $R_{z}(\theta)$:

$\text{\\{}{}\,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0}{}[1]{}\text{\bf,}\>{}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1}{}[1]{}\text{\\}}{}\;\text{>{}>}\;{}\text{\\{}{}\,\text{\bf
phase}(-\theta/2)*{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0}{}[1]{}\text{\bf,}\>{}\text{\bf
phase}(\theta/2)*{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1}{}[1]{}\text{\\}}{}$

Similarly, the following acts exactly as an $R_{y}(\theta)$:

$\text{\\{}{}\,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}i}{}[1]{}\text{\bf,}\>{}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}j}{}[1]{}\text{\\}}{}\;\text{>{}>}\;{}\text{\\{}{}\,\text{\bf
phase}(-\theta/2)*{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}i}{}[1]{}\text{\bf,}\>{}\text{\bf
phase}(\theta/2)*{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}j}{}[1]{}\text{\\}}{}$

Additionally, the following applies a global phase of $\theta$:

$\text{\\{}{}\,{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0}{}[1]{}\text{\bf,}\>{}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1}{}[1]{}\text{\\}}{}\;\text{>{}>}\;{}\text{\\{}{}\,\text{\bf
phase}(\theta)*{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0}{}[1]{}\text{\bf,}\>{}\text{\bf
phase}(\theta)*{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1}{}[1]{}\text{\\}}{}$

Then using a ZYZ decomposition (Nielsen and Chuang, 2010, §4.2), Mini-Qwerty
is capable of executing any one-qubit unitary by applying the aforementioned 3
functions with different choices of $\theta$.

Furthermore, a CNOT can be performed in Mini-Qwerty with the following basis
translation:

$\text{\\{}{}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1}{}[1]{}\text{\\}}{}\bm{+}{}\text{\\{}{}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0}{}[1]{}\text{\bf,}\>{}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1}{}[1]{}\text{\\}}{}\;\text{>{}>}\;{}\text{\\{}{}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1}{}[1]{}\text{\\}}{}\bm{+}{}\text{\\{}{}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}1}{}[1]{}\text{\bf,}\>{}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0}{}[1]{}\text{\\}}{}$

Thus, by the universality of single qubit gates and CNOTs (Nielsen and Chuang,
2010, §4.5.2), Mini-Qwerty is universal. ∎

###  A.5. Realization in the Python DSL

##### Syntax differences

Qwerty is largely an embedding of Mini-Qwerty in Python, but there are some
departures from the syntax in Fig. 21. The most notable is that application in
Qwerty is written as $e{}_{2}$ |$e{}_{1}$ rather than $e{}_{1}e{}_{2}$ as in
Mini-Qwerty (Fig. 21) — that is, the order is reversed from before, with the
input first and the function second. This change makes Qwerty code read from
left-to-right like a Unix shell pipeline, where earlier operations are written
before later operations. This pipeline-like style of programming avoids the
tedious repeated variable definitions common in languages with linear qubit
types (Paykin et al., 2017; Yuan et al., 2022). Fig. 27 shows an example of
this.

⬇ (* ... *) let (p0 : qubit<M>, p1 : qubit<M>) = p in let (p0 : qubit<M>, p1 :
qubit<M>) = (H p0, H p1) in let (p0 : qubit<M>, p1 : qubit<M>) = (Z p0, Z p1)
in let (p0 : qubit<M>, p1 : qubit<M>) = CZ (p0, p1) in let (p0 : qubit<M>, p1
: qubit<M>) = (H p0, H p1) in (* ... *)

(a) Twist: The diffuser in Grover’s algorithm (Yuan et al., 2022)

⬇ # ... q | pm[N] >> std[N] | -(’0’[N] >> -’0’[N]) | std[N] >> pm[N] # ...

(b) Qwerty: The diffuser in Grover’s algorithm written more verbosely than in
Fig. 3d

Figure 27. Side-by-side comparison of the Grover diffuser in Twist versus Qwerty to demonstrate the succinctness afforded by the pipe | operator.

Otherwise, Mini-Qwerty syntax is materialized in Qwerty using common Python
syntax: for example, the sequence $\mathbbm{q}{}$ is a Python string literal
containing only ’0’, ’1’, ’+’, ’-’, ’i’, and ’j’. (As discussed in Section
3.2.1, combined with qubit literals as string literals, the choice of $\bm{+}$
lines up with intuition of the tensor product as concatenation.) In Qwerty,
the types in Figure 21 are written similarly to typical Python type
annotations: $\mathrm{qubit}[n_{1}]{}\rightarrow{}\mathrm{qubit}[n_{2}]{}$ is
written as qfunc[$n_{1}$,$n_{2}$],
$\mathrm{qubit}[n_{1}]{}\xrightarrow{\text{rev}}{}\mathrm{qubit}[n_{2}]{}$ as
rev_qfunc[$n_{1}$,$n_{2}$], and
$\mathrm{bit}[n_{1}]{}\rightarrow{}\mathrm{bit}[n_{2}]{}$ as
cfunc[$n_{1}$,$n_{2}$].

##### Syntactic sugar

There are also several cases of syntactic sugar in Qwerty versus Mini-Qwerty:
in Qwerty, the unary operator - is equivalent to $\text{\bf phase}(\pi)*$, and
programmers can write $\mathbbm{q}$ instead of $\mathbbm{q}[n]{}$ to imply
$n=1$. Furthermore, a qubit literal $\mathbbm{q}{}[n]{}$ can be used wherever
a basis can be used and will automatically be promoted to a singleton basis
literal {$\mathbbm{q}[n]{}$}. Qwerty also supports writing a predicator as
$e{}\;\text{\&}\;{}b{}$ in addition to the $b{}\;\text{\&}\;{}e{}$ syntax
supported by Mini-Qwerty.

##### Classical functions

Mini-Qwerty focuses on code decorated with @qpu (Section 3.2.4), but as
discussed in Section 3.2.5, Qwerty also supports classical code decorated with
@classical. The type system for the @classical DSL is straightforward,
guaranteeing that e.g. binary bitwise operations are performed on bitvectors
with the same dimension. In the Qwerty @qpu DSL, a classical function f can be
instantiated using f.xor_embed, f.phase, or f.inplace(f_inv) as Section 3.2.5
describes. This means Qwerty extends Mini-Qwerty with more type rules in the
spirit of the following:

$\displaystyle\textstyle\small\Gamma{}\vdash_{0}f{}\text{\bf.xor\\_embed}{}(e{}):{}\mathrm{qubit}{}[n_{1}+n_{2}]{}\xrightarrow{\text{rev}}{}\mathrm{qubit}{}[n_{1}+n_{2}]{}\Gamma{}\vdash_{0}f{}:{}\mathrm{bit}{}[n_{1}]{}\rightarrow{}\mathrm{bit}{}[n_{2}]{}$

##### Qwerty type checking

When type-checking the body of a Qwerty @qpu kernel, the type context
$\Gamma{}$ is initialized with the types of captures and arguments, and the
resulting type of the expression should match the result type defined by the
function signature. Type checking fails when a @qpu kernel calls a non-
reversible function yet is decorated with @reversible to indicate its type is
$\tau_{1}\xrightarrow{\text{rev}}\tau_{2}{}$ (e.g., line 4 of Fig. 18 in
Section 4.3.2). Note that while naïvely implementing basis-related checks
based on definitions in Fig. 25 could cause type checking to take time
exponential in the number of qubits, the Qwerty compiler uses straightforward
optimizations to prevent this.

##### Semantic differences

In Qwerty, $\text{\bf phase}(\theta){*}{}$ can be applied to functions (e.g.,
$\text{\bf phase}(\theta)*{}\text{\bf id}{}$), whereas $\text{\bf
phase}(\theta){*}{}$ can only be applied to qubits in Mini-Qwerty (e.g.,
$\text{\bf
phase}(\theta)*{}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}0}[1]{}$).
More significantly, the Ediscard rule in Fig. 26 describes the intent of
discard faithfully in abandoning its qubit operand, but in a realistic,
efficient implementation, reusing discarded qubits is crucial. There are two
situations where a programmer would discard a qubit: (1) at the end of an
algorithm when the measurement result of a dirty qubit is unneeded, as seen in
many of the examples in Section 4; and (2) returning a clean
($\left|0\right\rangle$) qubit to the pool of ancilla qubits maintained by the
quantum runtime. In Qwerty, the discard built-in function handles case (1) and
resets a qubit to $\left|0\right\rangle$ using measurement; the discardz
built-in handles case (2) and returns the qubit to the ancilla pool without
measurement.