```
Author: Lars HellstrÃ¶m <[email protected]>
State: Draft
Type: Project
Vote: Pending
Tcl-Version: 9.2
Created: 01-Apr-2006
Post-History:
```

# Abstract

A new Tcl command **qubit** is proposed. This command makes it possible to
handle quantum information in the form of qubits.

# Rationale

As stated in [131], what Tcl needs in order to succeed in the marketplace is a
feature that no other programming language provides, a "killer app" as it
were. The Tk toolkit, Expect, cross-platform portability, starkits, tkcon, and
excellent embed/extend-ability with respect to other languages are all well
and good, but they have clearly failed to push Tcl usage to the point of
having critical mass. The **qubit** command makes it possible to achieve an
exponential speedup for important problems and should therefore provide a
powerful enough incentive that even Perl programmers would be compelled to
switch languages.

# Background

Quantum computing makes use of phenomena in quantum mechanics to, at each time step, carry out an exponential amount of work using only a linear amount of hardware. The way this maps onto physical reality is pretty mind-boggling, but for the programmer it is sufficient to think of the Quantum Processing Unit (QPU) as an extremely powerful but somewhat specialised coprocessor and leave it at that. (Chances are anyway that the QPU isn't physically located in your desktop computer, as they tend to involve lots of lasers, magnets, vacuum chambers, liquid nitrogen cooling, etc.)

Quantum information display an interesting duality in that it is analog during a computation, but becomes digital as soon as one measures it. (Wave/particle duality, in case anyone came to think of that, is the kind of "mapping onto physical reality" issue that will not be treated here.) This makes the design of quantum algorithms somewhat different from the design of classical algorithms, in a manner similar to that in which the design of analog electronic circuits is different from the design of digital electronic circuits, as one must often work out the numbers rather than rely on a discrete case-by-case analysis. Another curious feature is that all fully quantum operations must be reversible, which in particular has the effect that quantum information can neither be duplicated nor (in the absence of measurements) destroyed, only rearranged. There is in particular no quantum analogue to assignments such as [set a $b], since not only need this copy the value of b, it also irrecoverably destroys the old value of a; the closest one gets to such an assignment is exchanging the values of a and b.

For more information on quantum computing in general, see e.g.:

Wikipedia article "Quantum computer" http://en.wikipedia.org/wiki/Quantum_computer .

J. Gruska: Quantum Computing (1999), ISBN 0-07-709503-0, http://www.fi.muni.cz/usr/gruska/quantum/ .

# Specification

The quantum computing model supported by the **qubit** command is that of
*quantum bits* (more commonly called *qubits*) and *quantum boolean
circuits*. While other more fancy models such as "Quantum Turing Machines"
exist, this is generally considered to be the most realistic model, and it is
also the one most closely related to the number-of-gates complexity measure
for classical computing. Should it in the future prove desirable to support
also some other model, then one may do so through a separate command.

In this model, a quantum state of N qubits is completely specified by a set of
2**N complex numbers, usually known as *probability amplitudes* (they are
not probabilities as such, but they do completely determine the probabilities
for various events). Many different bases are possible, but in the standard
(also known as the computational) basis each of these amplitudes corresponds
to a particular assignment of 0s and 1s to the qubits. Operations on a quantum
state can be understood as operations on the vector of amplitudes.

The **qubit** command has the five subcommands.

## The 'new' Subcommand

qubit new?-option value?...??

Allocate/create a new qubit, and return a handle for the new qubit that identifies it in subsequent operations, or throw an error if allocation/creation failed (possible causes include, but are not limited to, lack of resources on the hardware side and user having insufficient permissions). New qubits are not entangled with any of the old ones, but their state is otherwise unspecified.

The options are meant as a means for supplying extra information about the new qubit, such as for example whether it is being protected from decoherence by a scheme of quantum error correction codes (the Tcl core can easily implement such features on platforms where the C level APIs only provide raw qubits); however at present no options are defined.

## The 'operate' Subcommand

qubit operategate id0?id1?...??

Perform a quantum operation (the *gate*) on one or more qubits (specified
using the handles *id0*, *id1*, etc.). Returns the operation actually
applied.

In the interest of generality, gates are specified as unitary matrices (this is a universal representation for quantum gates), or more concretely as lists of lists of lists of doubles. The innermost lists must have length 2 and encode the real (index 0) and imaginary (index 1) parts of an element of the matrix. Indices in the middle list level select a column and indices in the outer list level consequently a row. Put another way,

```
lindex $gate $i $j 0 ; # Returns Re gate(i,j)
lindex $gate $i $j 1 ; # Returns Im gate(i,j)
```

The row/column index corresponding to the *id0* qubit having value $r0, the
*id1* qubit having value $r1, etc. is $r0*(2**0) + $r1*(2**1) + ... A
*gate* for operating on *n* qubits must thus have side 2***n*. Columns
correspond to qubit states before the operation and rows correspond to qubit
states after the operation.

An error is thrown if the number of qubit arguments does not match the side of
the *gate* matrix, if not all *idN* arguments are qubit handles, if some
qubit occurs twice in the list, and if *gate* is not a proper matrix (too
many or too few elements in some list, elements not recognised as doubles,
etc.).

An error is *not* thrown if the *gate* is not unitary. In general the
operation actually applied has to be supported by the available hardware, so
the **qubit operate** command (or some lower level interface) should
determine which supported operation most closely approximates the specified
*gate* and apply that instead. The user can check what was done (up to
numeric precision) by inspecting the return value. Using a return value from
**qubit operate** as the *gate* for another call should result in the
exact same operation being carried out.

## The 'measure' Subcommand

qubit measureid

Measures a qubit with respect to the standard basis. Returns 0 or 1 depending on the resulting state.

*Note* that measuring a qubit changes the quantum state to one in which that
qubit has a pure value. If other qubits are initially entangled with the one
being measured, then these will also be affected by this operation. Measuring
a qubit causes it to be disentangled from all other qubits (or perhaps
entangles the state of the entire universe with the qubit, depending on your
philosophical point of view).

## The 'dispose' Subcommand

qubit disposeid

Frees/deallocates a qubit, returning it to whatever pool of resources **qubit
new** got it from, but before doing that the qubit is measured to safely
disentangle it from any remaining qubits. The return value is 0 or 1 as for
the corresponding **qubit measure**.

## The 'names' Subcommand

qubit names

This is an instrospection command. It returns a list of all qubit handles currently available in this interpreter.

## Future Expansion

Other subcommands may be added in the future, but this set is complete for single interpreter algorithms.

# Examples

The syntax of **qubit operate** was chosen to facilitate the creation of
aliases for common gates, as this should make programs more readable. An alias
for the CNOT (conditional not) gate can be created as

```
interp alias {} CNOT {} qubit operate {
{ {1 0} {0 0} {0 0} {0 0} }
{ {0 0} {0 0} {0 0} {1 0} }
{ {0 0} {0 0} {1 0} {0 0} }
{ {0 0} {1 0} {0 0} {0 0} }
}
```

after which one can use the command

```
CNOT $control $target
```

The more significant $target qubit is negated if the $control qubit is 1 but left alone otherwise.

Another standard gate is the Hadamard gate, which can be defined as follows.

```
set rsqrt2 [list [expr {1/sqrt(2)}] 0] ; # Reciprocal square root of 2.
interp alias {} Hadamard {} qubit operate [
list [list $rsqrt2 $rsqrt2] [list $rsqrt2 [list [expr -sqrt(0.5)] 0]]
]
```

The Hadamard gate is used to create states that are uniform superpositions of 0s and 1s. A simple application of that is the following random bit generator.

```
proc randombit {} {
set id [qubit new] ; # Allocate qubit
qubit measure $id ; # Make pure 0 or pure 1
Hadamard $id ; # Make an equal mix of 0 and 1
return [qubit dispose $id]; # Measure and clean up
}
```

Note that this (provided, of course, that one believes in the standard interpretation of quantum mechanics) is not a psuedo-random bit generator, but a truly random bit generator. Even if the Hadamard gate would be slightly off (unlikely, as this is a very standard gate, but possible) this would not affect the essential randomness of the bits produced, but only the exact probability.

A third type of elementary gate is the phase shift gate, which changes the phase (but not the size) of some probability amplitude. To change the phase of the 1 amplitude of a qubit $id by the angle $phi, one would use the command

```
qubit operate [list {{1.0 0.0} {0.0 0.0}} [list {0.0 0.0} [
list [expr {cos($phi)}] [expr {sin($phi)}]
]]] $id
```

Phase changes do not change the probability distribution for any qubit measurement, but they do affect the state in ways that can lead to different probabilities further on, and thus illustrate the fact that there is more to a quantum state than the probability distribution it gives rise to here and now. As a concrete example of this, assuming $id is a qubit, and with aliases as above, the script:

```
set before [qubit measure $id]
Hadamard $id
Hadamard $id
set after [qubit measure $id]
expr {$before == $after}
```

will with probability 1 produce the result 1, whereas the script:

```
set before [qubit measure $id]
Hadamard $id
qubit operate {{{1 0} {0 0}} {{0 0} {-1 0}}} $id
Hadamard $id
set after [qubit measure $id]
expr {$before == $after}
```

will with probability 1 produce the result 0. The only difference is the 180
degrees phase shift of the 1 amplitude in the explicit **qubit operate**
command, which transforms one state with equal probabilities for 0 and 1 to
another state with equal probabilities for 0 and 1!

# Rejected Alternatives

One might expect that a truly Quantum Tcl would keep quantum information as "first class data", i.e., in Tcl_Objs to be passed around by value rather than as qubits that can only be passed around by name, but that is impossible (unless one goes to such lengths as to run the entire Tcl process in a QPU, which again will probably never be possible) due to a fundamental incompatibility between the laws of quantum mechanics and Tcl's Everything Is A String principle.

Beginning with the EIAS side, one may observe that for a quantum state to be encodable into a Tcl_Obj, it must be serializable - there must be a way of generating a string that completely encodes the state. Since quantum mechanics does not permit extracting that much information about a quantum state, there are only two options: either everything is kept within the QPU (not realistic), or nothing is kept in the QPU. In the latter case, one loses entirely the advantage of quantum computation, so it is rather pointless.

On the quantum side, one may observe that most of the things that are routinely done to Tcl_Objs are simply impossible to do to quantum information. The fundamental problem here is that Tcl_Objs must be duplicatable, whereas it is a theorem in quantum mechanics that quantum states cannot be duplicated (the "No cloning" theorem). Somewhat related is the problem that quantum information can only be read (used as input to some operation) once, whereas a Tcl_Obj can be written once but read an unlimited number of times.

# Security Implications

As the **qubit** command only manipulates data and cannot be used for any
form of communication, it may in principle be made available also in safe
interpreters. However since **qubit new** seizes a global resource that can
be expected to be in limited supply on a system, it is probably better to be
safe than sorry, and therefore the **qubit** command shall initially be
hidden in a safe interpreter.

Omitting the command entirely and instead alias all qubit operations to the
**qubit** command of the parent interpreter is *not* a good idea, as the
quick (but sloppy) implementation of this would allow untrusted code evaluated
in the safe interpreter access also to the qubits of the parent.

It should be noted that the easy access to quantum computing that this command provides would have significant implications for the security of many external systems. Such issues are outside the scope of this TIP.

# Future Extensions

Besides quantum algorithms, many interesting applications of quantum
information processing involves communication through the means of a quantum
state shared by different parties. While fast long distance qubit
transportation is physically made possible by means of quantum teleportation
(which really isn't as fancy as it sounds - basically it amounts to a
combination of the old TV chef trick of having prepared something in advance,
in this case physically transferring a qubit, and the patchfile trick of only
transmitting a diff against what was physically distributed), there are
currently no standardised protocols for this, and until the time that there is
there probably isn't much point in specifying some **qubit socket** command
for Tcl either. It may however be observed that *non-open* commercial
systems http://www.magiqtech.com/ transmitting quantum information over long
distances are available today.

While transferring qubits between different machines obviously present some technical problems, it may seem that transferring qubits between different interpreters in the same process should at least be straightforward, but the presence of multiple threads in the process introduce complications also for this case. Concretely, transferring a qubit from one thread to another will in general cause these threads to become entangled! In order to not make thread maintenance even more complicated by introducing the concept of quantum deadlock due to thread tangles, this TIP does not treat the subject of a mechanism for transferring qubits between interpreters.

# Reference Implementation

A Tcl level emulation of the **qubit** command (minus some error checking,
but also not requiring a QPU) is available as SF patch no 1462755
http://sf.net/tracker/?func=detail&aid=1462755&group_id=10894&atid=310894 .
This emulation uses the standard Tcl rand() function for generating random
numbers, so it is not cryptographically safe. Also note that it internally
uses of some tcllib packages, which must therefore be available.

No C implementation exists at present, but creating one is a simple matter of
programming (SMOP). In particular, since the details of the command
implementations for the foreseeable future almost surely will have some
dependence on the particular hardware present, it seems appropriate to assign
to each subcommand an entry in the internal stubs table and then simply have
the main *Tcl_QubitObjCmd* call each as appropriate.

```
int
Tcl_QubitObjCmd(
ClientData clientData, /* Might be used. */
Tcl_Interp *interp, /* Current interpreter. */
int objc, /* Number of arguments. */
Tcl_Obj *CONST objv[]) /* Argument objects. */
{
int index;
static CONST char *options[] = {
"dispose", "measure", "names",
"new", "operate", (char *) NULL
};
enum options {
QUBIT_DISPOSE, QUBIT_MEASURE, QUBIT_NAMES,
QUBIT_NEW, QUBIT_OPERATE
};
if (objc < 2) {
Tcl_WrongNumArgs(interp, 1, objv, "subcmd ?arg ...?");
return TCL_ERROR;
}
if (Tcl_GetIndexFromObj(interp, objv[1], options, "subcommand", 0,
&index) != TCL_OK) {
return TCL_ERROR;
}
switch ((enum options) index) {
case QUBIT_DISPOSE:
return TclQubitDisposeObjCmd(clientData, interp, objc, objv);
case QUBIT_MEASURE:
return TclQubitMeasureObjCmd(clientData, interp, objc, objv);
case QUBIT_NAMES:
return TclQubitNamesObjCmd(clientData, interp, objc, objv);
case QUBIT_NEW:
return TclQubitNewObjCmd(clientData, interp, objc, objv);
case QUBIT_OPERATE:
return TclQubitOperateObjCmd(clientData, interp, objc, objv);
}
/*
* We won't get this far.
*/
Tcl_Panic("unhandled subcommand");
return TCL_ERROR;
}
```

A fallback definition of *TclQubitNewObjCmd* that can be used when Tcl is
compiled without hardware QPU support is:

```
int
TclQubitNewObjCmd(
ClientData dummy, /* Not used. */
Tcl_Interp *interp, /* Current interpreter. */
int objc, /* Number of arguments. */
Tcl_Obj *CONST objv[]) /* Argument objects. */
{
int optArgIdx, index;
static CONST char *optionStrings[] = {
(char *) NULL /* Currently there are no options. */
};
if (objc % 2 != 0) {
Tcl_WrongNumArgs(interp, 2, objv, "?-option value ...?");
return TCL_ERROR;
}
for (optArgIdx = 2 ; optArgIdx < objc ; optArgIdx += 2) {
if (Tcl_GetIndexFromObj(interp, objv[optArgIdx], optionStrings,
"option", TCL_EXACT, &index) != TCL_OK) {
return TCL_ERROR;
}
/*
* When options are added, handle them here.
*/
}
/*
* Fail gracefully.
*/
Tcl_SetErrno(ENXIO); /* QPU not configured. */
Tcl_AppendResult(interp, "couldn't allocate a qubit: ",
Tcl_PosixError(interp), NULL);
return TCL_ERROR;
}
```

Other fallback definitions obviously follow the same pattern. Filling in the details should be a cultivating exercise for Robert Abitbol.

# Copyright

This document has been placed in the public domain.