TIP: 263 Title: Quantum Tcl Version: $Revision: 1.2 $ Author: Lars Hellström 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 operate''' ''gate 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 measure''' ''id'' 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 dispose''' ''id'' 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.