Introduction

A programmable device is a machine whose behavior can be changed without rebuilding the machine. A familiar classical example is a laptop: the physical hardware stays roughly the same, while a program changes whether the device behaves like a calculator, a text editor, or a video player. The central question of this book is what happens when the device, the data, and the program are quantum systems.

At first this may sound like a small variation on ordinary quantum computing. It is not. In the usual circuit model, we often describe a quantum computer by saying, “apply this gate, then that gate,” as if the choice of gate were controlled by an external classical instruction. In a programmable quantum device, the instruction itself may be a quantum state. The device has a fixed physical interaction, but different program states are intended to make it implement different quantum operations, measurements, or higher-order transformations.

This shift creates a deep tension. Quantum states can be superposed and entangled, so one might hope that quantum programs are more flexible than classical programs. But quantum states also cannot, in general, be perfectly distinguished unless they are orthogonal. This fact is one of the roots of the no-programming theorem, which says, in one important form, that a deterministic exact processor implementing distinct unitary channels must use mutually orthogonal program states (Nielsen and Chuang, 1997). Thus, a finite-dimensional quantum program register cannot exactly and deterministically program all possible unitary operations on even a single qubit.

This book develops that result slowly, from first principles, and then moves beyond it. We will study not only programmable unitary gates, but also programmable channels, measurements, instruments, and higher-order quantum devices.

The basic picture

A quantum device acts on a quantum system. In finite-dimensional quantum theory, a system is represented by a complex vector space with an inner product, called a Hilbert space. A two-level quantum system, or qubit, has a Hilbert space isomorphic to \(\mathbb{C}^2\). A state of the qubit may be represented by a unit vector such as

\[ |\psi\rangle = \alpha |0\rangle + \beta |1\rangle, \]

where \(\alpha,\beta \in \mathbb{C}\) and

\[ |\alpha|^2 + |\beta|^2 = 1. \]

The numbers \(|\alpha|^2\) and \(|\beta|^2\) are probabilities for the outcomes \(0\) and \(1\) if the qubit is measured in the computational basis. More general quantum states, including states that represent classical uncertainty or subsystems of entangled states, are described by density operators. These are positive semidefinite operators with trace one. This density-operator formalism is standard in quantum information theory because it treats pure states, mixed states, and composite systems in one language (Nielsen and Chuang, 2010; Watrous, 2018).

A quantum operation that takes input states to output states is called a quantum channel when it is physically allowed and deterministic. Mathematically, a finite-dimensional quantum channel is a linear map

\[ \Phi : \mathcal{L}(\mathcal{H}_{\mathrm{in}}) \to \mathcal{L}(\mathcal{H}_{\mathrm{out}}) \]

that is completely positive and trace preserving. Here \(\mathcal{L}(\mathcal{H})\) denotes the space of linear operators on the Hilbert space \(\mathcal{H}\). “Trace preserving” means that total probability remains one. “Completely positive” means that the operation remains positive even when it acts on only part of a larger entangled system. Complete positivity is not a decorative technical condition; it is needed because quantum systems may be correlated with external systems that the device does not directly touch (Watrous, 2018).

A simple example is the identity channel:

\[ \operatorname{id}(\rho)=\rho. \]

It leaves every input state unchanged. Another example is a unitary channel,

\[ \Phi_U(\rho)=U\rho U^\dagger, \]

where \(U\) is a unitary operator. This is the mathematical form of a closed, reversible quantum evolution.

A programmable quantum processor tries to implement many such maps using one fixed physical mechanism. A basic deterministic model looks like this:

\[ \mathcal{P}_\sigma(\rho) = \operatorname{Tr}_{\mathrm{P}} \left[ V(\rho \otimes \sigma)V^\dagger \right]. \]

Here:

• \(\rho\) is the input state of the data system.
• \(\sigma\) is the program state.
• \(V\) is a fixed unitary interaction between the data system and the program system.
• \(\operatorname{Tr}_{\mathrm{P}}\) means that the program system is discarded after the interaction.

The processor is “programmable” because changing \(\sigma\) changes the induced channel \(\mathcal{P}_\sigma\). The hardware \(V\) is fixed; the program state is the instruction.

For example, one program state might aim to make the processor apply the Pauli \(X\) operation to a qubit,

\[ X|0\rangle = |1\rangle, \qquad X|1\rangle = |0\rangle, \]

while another program state might aim to make the same processor apply the Pauli \(Z\) operation,

\[ Z|0\rangle = |0\rangle, \qquad Z|1\rangle = -|1\rangle. \]

The question is not whether one can build a circuit that applies \(X\) or \(Z\). Of course one can. The question is subtler: can one fixed quantum interaction implement many different operations merely by receiving different quantum program states?

Why programmability is not automatic

In classical computation, distinct programs can be stored as distinct bit strings. A finite memory with \(n\) bits stores \(2^n\) perfectly distinguishable programs. If we need more programs, we add more bits. There is no obstacle in principle to reading the program without disturbing it, copying it, or checking whether two program strings are equal.

Quantum programs behave differently. Two quantum states \(|\phi\rangle\) and \(|\psi\rangle\) are perfectly distinguishable in a single measurement only when they are orthogonal:

\[ \langle \phi|\psi\rangle = 0. \]

If they are not orthogonal, no measurement can identify them with certainty in one shot. This is closely connected to the impossibility of cloning arbitrary unknown quantum states and to the geometry of quantum state space, both central themes in quantum information theory (Nielsen and Chuang, 2010).

This has immediate consequences for programming. If a processor must exactly implement two distinct unitary operations in a deterministic way, then the corresponding program states must be perfectly distinguishable; hence they must be orthogonal. This is the core content of the Nielsen–Chuang no-programming theorem for unitary channels (Nielsen and Chuang, 1997). Since a finite-dimensional program Hilbert space contains only finitely many mutually orthogonal states, exact deterministic universal programming of all unitary operations requires an infinite-dimensional program space.

This result is not a failure of engineering. It is a structural theorem about quantum mechanics.

Still, the theorem does not end the subject. Instead, it opens several research directions:

1. What if we only need approximate programming?
2. What if the processor is allowed to fail sometimes, but announces when it succeeds?
3. What if the target devices are not unitary gates, but noisy quantum channels?
4. What if we want to program measurements rather than state transformations?
5. What if the program contains entanglement or is used adaptively?
6. What if the object being transformed is itself a quantum operation?

Each of these questions leads to a different mathematical model and a different notion of resource cost.

Operations, measurements, and instruments

A quantum device may transform a system, measure it, or do both. These possibilities must be carefully separated.

A channel describes a transformation of quantum states when no measurement outcome is recorded. For example, a noisy memory might take a qubit state \(\rho\) and output

\[ \Phi(\rho) = (1-p)\rho + p X\rho X, \]

which means that with probability \(p\) a bit-flip error occurs.

A measurement describes the probabilities of possible outcomes. In modern quantum theory, general measurements are represented by positive operator-valued measures, or POVMs. A finite-outcome POVM is a collection of positive semidefinite operators

\[ \{E_a\}_{a \in A} \]

such that

\[ \sum_{a \in A} E_a = I. \]

If the system is in state \(\rho\), the probability of outcome \(a\) is

\[ p(a)=\operatorname{Tr}(E_a\rho). \]

This is Born’s rule in the POVM formalism. POVMs include ordinary projective measurements but also describe more general measurement procedures, including measurements obtained by coupling the system to an ancilla and then measuring the larger system (Heinosaari and Ziman, 2012).

For example, measuring a qubit in the computational basis corresponds to the two effects

\[ E_0 = |0\rangle\langle 0|, \qquad E_1 = |1\rangle\langle 1|. \]

But a less sharp binary measurement may be described by

\[ E_0 = q |0\rangle\langle 0| + (1-q)|1\rangle\langle 1|, \]

\[ E_1 = (1-q)|0\rangle\langle 0| + q |1\rangle\langle 1|, \]

where \(1/2 \le q \le 1\). When \(q=1\), the measurement is sharp in the computational basis. When \(q=1/2\), the outcome is completely uninformative.

An instrument combines both aspects: it gives the probability of each measurement outcome and the post-measurement state conditioned on that outcome. Instruments are necessary when a device both extracts information and disturbs the system. The distinction between a POVM and an instrument is important: the same measurement statistics may arise from different physical procedures that leave different output states (Heinosaari and Ziman, 2012).

Programmable measurement devices therefore raise questions beyond programmable channels. A program state might determine the effects \(\{E_a\}\), the post-measurement transformations, or both. A device that only reproduces the correct outcome probabilities is weaker than a device that reproduces the full instrument.

Dilation: the hidden simplicity behind open dynamics

Two dilation theorems form part of the backbone of this book.

A dilation theorem says that a complicated-looking process on a system can be represented as a simpler process on a larger system. The larger system may include an environment, an ancilla, or an extended measurement space. The word “dilation” means that we enlarge the mathematical setting so that the process becomes easier to understand.

The Stinespring dilation theorem says, in finite-dimensional language, that every quantum channel can be implemented by an isometry into a larger space, followed by discarding an environment. Equivalently, many noisy or irreversible processes can be understood as arising from reversible dynamics on a larger closed system (Stinespring, 1955; Watrous, 2018).

A simple example is the bit-flip channel

\[ \Phi(\rho)=(1-p)\rho+pX\rho X. \]

We can imagine an environment qubit that records whether an error occurred. A suitable isometry \(A\) acts as

\[ A|\psi\rangle = \sqrt{1-p}\,|\psi\rangle \otimes |0\rangle + \sqrt{p}\,X|\psi\rangle \otimes |1\rangle. \]

If we discard the environment, we obtain exactly the bit-flip channel. The environment contains information about which branch occurred, but if we do not observe it, the system appears noisy.

The Naimark dilation theorem says that every POVM can be realized as a projective measurement on a larger Hilbert space. In other words, generalized measurements can be understood as ordinary sharp measurements after adjoining an ancilla and applying a suitable interaction (Heinosaari and Ziman, 2012).

For example, an unsharp qubit measurement can be implemented by coupling the qubit to an ancilla and then performing a projective measurement on the enlarged system. The POVM description records only the effective statistics on the original qubit.

These dilation theorems are not merely technical tools. They explain why programmable devices have the forms they do. A programmable channel can be studied through a fixed interaction with a program and an environment. A programmable measurement can be studied through a fixed measurement on a larger system whose effective POVM depends on the program state. Stinespring and Naimark dilation turn physical implementation questions into precise linear-algebraic questions.

Exact, approximate, and probabilistic programming

When studying programmability, we must state what kind of success we require.

In exact deterministic programming, the processor must always implement the target device perfectly. If the target is a unitary channel \(\Phi_U(\rho)=U\rho U^\dagger\), then the programmed processor must satisfy

\[ \mathcal{P}_{\sigma_U}(\rho)=U\rho U^\dagger \]

for every input state \(\rho\). This is the setting of the original no-programming theorem for unitary channels (Nielsen and Chuang, 1997).

In approximate programming, we allow error. The processor may implement a channel \(\widetilde{\Phi}\) close to the target channel \(\Phi\). But “close” must be defined carefully. For quantum channels, a powerful operational metric is the diamond norm, which measures distinguishability even when the input system may be entangled with an external reference system (Watrous, 2018). Approximate programming changes the problem from “is perfect universality possible?” to “how large must the program system be to achieve error at most \(\varepsilon\)?”

In probabilistic programming, the processor may fail, but it includes a classical success flag. If the success flag appears, the conditional output must be correct. This model is different from ordinary approximation: a successful run may be exact, but success occurs only with some probability. Probabilistic programmable gates were studied as a way to store or implement quantum dynamics using quantum states, with success probability becoming a central resource parameter (Vidal, Masanes, and Cirac, 2002).

In heralded programming, failure or success is announced by a measurement outcome. “Heralded” means that the user knows whether the attempt succeeded. This is crucial: an unannounced failure is noise, while an announced failure can be discarded or retried.

For example, suppose a processor tries to implement a target unitary \(U\). It may produce a classical flag \(s \in \{\mathrm{success},\mathrm{failure}\}\). If \(s=\mathrm{success}\), the output state is exactly \(U\rho U^\dagger\). If \(s=\mathrm{failure}\), the output may be unusable, but the user knows this and can reject that run. Such a device is not deterministic, but it may still be valuable.

Programmable measurements

Programmable measurements are subtler than they first appear. A measurement device may have a fixed interaction and a fixed final detector, while the program state changes the effective POVM on the data system.

Imagine a qubit measurement apparatus with two outcomes, \(0\) and \(1\). With one program state, it measures approximately in the computational basis. With another program state, it measures approximately in the Hadamard basis,

\[ |+\rangle = \frac{|0\rangle+|1\rangle}{\sqrt{2}}, \qquad |-\rangle = \frac{|0\rangle-|1\rangle}{\sqrt{2}}. \]

The computational-basis measurement has effects

\[ |0\rangle\langle 0|, \qquad |1\rangle\langle 1|, \]

while the Hadamard-basis measurement has effects

\[ |+\rangle\langle +|, \qquad |-\rangle\langle -|. \]

Can one fixed apparatus implement both exactly using nonorthogonal program states? Can it implement all qubit projective measurements with a finite-dimensional program register? What changes if approximation is allowed?

These questions were developed in the theory of programmable multimeters and programmable quantum measurements, where one studies how program states determine measurement statistics and what dimensional resources are necessary (D’Ariano, Perinotti, and Sedlák, 2006). Measurement programming is not just channel programming with different notation. A channel is judged by its action on states, while a measurement is judged by the probability distributions it produces, and an instrument is judged by both probabilities and conditional state transformations.

Naimark dilation gives a useful way to think about these devices. If every POVM can be realized by a projective measurement on a larger system, then programming a POVM can be viewed as programming part of that larger realization. But the same theorem also helps reveal limitations: if a fixed larger measurement is used, the program state must carry enough distinguishable information to select among the desired effective measurements.

Why finite dimensions come first

This book focuses first on finite-dimensional systems. This is not because infinite-dimensional quantum theory is unimportant. Photonic modes, continuous variables, and many realistic systems require infinite-dimensional Hilbert spaces. But finite dimensions allow us to see the main ideas without analytic complications.

In finite dimensions:

• linear maps can be represented by matrices;
• positive operators have spectral decompositions;
• channels have Kraus representations;
• POVMs are finite collections of positive semidefinite matrices;
• many optimization problems can be expressed as semidefinite programs;
• dilation theorems can be proved with linear algebra.

This makes finite-dimensional theory the right first training ground. Once the finite-dimensional structure is clear, the reader can better understand which parts extend to infinite-dimensional settings and which require additional care.

A roadmap of the book

The book begins with the problem of quantum programmability itself. We ask what it would mean for one fixed device to implement many possible operations or measurements, and why quantum theory makes this difficult.

Chapters 2 and 3 build the linear algebra and quantum-state formalism needed for the rest of the book. We will study vector spaces, tensor products, adjoints, projections, density operators, composite systems, entanglement, purification, and Schmidt decomposition.

Chapters 4 and 5 introduce measurements and channels. These chapters provide the language of POVMs, instruments, completely positive maps, Kraus operators, and Choi matrices.

Chapter 6 develops tools for comparing states, measurements, and channels. Programmability is closely tied to distinguishability: if two target devices are very different, then their program states must carry enough distinguishable information to select between them.

Chapters 7 through 10 explain dilation and realistic measurement dynamics. Stinespring dilation shows how channels arise from unitary interactions with environments. Naimark dilation shows how POVMs arise from projective measurements on larger systems. Instruments unify transformations and measurements.

Chapters 11 and 12 introduce the standard programmable processor model and prove the no-programming theorem for unitary channels. This is the first major impossibility result of the book.

Chapters 13 and 14 extend the discussion to general channels and programmable measurements. These chapters move closer to research-level questions, where unitary gates are only one part of the story.

Chapters 15 and 16 study probabilistic, heralded, and approximate programming. Here the central issue becomes resource tradeoff: how program dimension, success probability, and approximation error constrain one another.

Chapter 17 discusses universal approximate constructions, including teleportation-based ideas and port-based teleportation. Port-based teleportation provides a way to approximate universal programmable processors, but its resource scaling is substantial, making it a useful example of the difference between possibility and efficiency (Ishizaka and Hiroshima, 2008).

Chapter 18 introduces quantum supermaps, combs, and higher-order devices. These are transformations whose inputs and outputs may themselves be quantum operations. Such frameworks are important for describing adaptive networks and higher-order processing of quantum devices (Chiribella, D’Ariano, and Perinotti, 2009).

The final chapters connect programmability to learning, estimation, compiling, resource theories, physical architectures, and research methods. The goal is not only to understand known theorems, but also to prepare the reader to read and contribute to current research.

What you should expect to gain

By the end of this book, you should be able to read a paper on programmable quantum devices and identify:

• the data Hilbert space;
• the program Hilbert space;
• the fixed processor map;
• the family of target operations or measurements;
• whether programming is exact, approximate, deterministic, probabilistic, or heralded;
• the error metric or success criterion;
• the relevant dilation theorem;
• the resource being bounded, such as program dimension, entanglement, or number of ports;
• the operational meaning of the result.

You should also be able to recognize the common proof patterns. Many impossibility proofs begin by showing that different target devices require distinguishable program states. Many possibility proofs construct a fixed interaction and then analyze how well the chosen program family approximates the desired target family. Many modern results use convexity, Choi representations, semidefinite programming, or dilation theory.

The subject is mathematically precise, but its central intuition is simple:

A programmable quantum device is a fixed physical process whose behavior is controlled by a state. Quantum theory limits such devices because states are not ordinary classical labels.

Understanding that sentence deeply will take us through channels, measurements, dilations, no-programming theorems, and research-level models of programmable quantum technology.

References

Chiribella, G., D’Ariano, G. M., and Perinotti, P. (2009). “Theoretical framework for quantum networks.” Physical Review A, 80, 022339.

D’Ariano, G. M., Perinotti, P., and Sedlák, M. (2006). “Quantum measurements and programmable multimeters.” Journal of Mathematical Physics, 47, 092101.

Heinosaari, T., and Ziman, M. (2012). The Mathematical Language of Quantum Theory: From Uncertainty to Entanglement. Cambridge University Press.

Ishizaka, S., and Hiroshima, T. (2008). “Asymptotic teleportation scheme as a universal programmable quantum processor.” Physical Review Letters, 101, 240501.

Nielsen, M. A., and Chuang, I. L. (1997). “Programmable quantum gate arrays.” Physical Review Letters, 79, 321–324.

Nielsen, M. A., and Chuang, I. L. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press.

Stinespring, W. F. (1955). “Positive functions on C-algebras.” Proceedings of the American Mathematical Society*, 6(2), 211–216.

Vidal, G., Masanes, L., and Cirac, J. I. (2002). “Storing quantum dynamics in quantum states: A stochastic programmable gate.” Physical Review Letters, 88, 047905.

Watrous, J. (2018). The Theory of Quantum Information. Cambridge University Press.