Construction of a universal quantum computer

We construct a universal quantum computer following Deutsch’s original proposal of a universal quantum Turing machine (UQTM). Like Deutsch’s UQTM, our machine can emulate any classical Turing machine and can execute any algorithm that can be implemented in the quantum gate array framework but under the control of a quantum program, and hence is universal. We present the architecture of the machine, which consists of a memory tape and a processor and describe the observables that comprise the registers of the processor and the instruction set, which includes a set of operations that can approximate any unitary operation to any desired accuracy and hence is quantum computationally universal. We present the unitary evolution operators that act on the machine to achieve universal computation and discuss each of them in detail and specify and discuss explicit program halting and concatenation schemes. We define and describe a set of primitive programs in order to demonstrate the universal nature of the machine. These primitive programs facilitate the implementation of more complex algorithms and we demonstrate their use by presenting a program that computes the NAND function, thereby also showing that the machine can compute any classically computable function.

Figure 1

Architecture of the universal quantum computer $\mathcal{U}\mathcal{Q}\mathcal{C}$, showing the memory tape $M$, processor $\mathcal{Q}$, address of tape head $|x⟩$, scratch qubit $|s⟩$, instruction register $|I⟩$, program address register $|P⟩$, data address register $|D⟩$, history address register $|H⟩$, flow control register $|F⟩$, halt qubit $|h⟩$, and the qubits that are measured ($|M⟩$ and $|h⟩$).

Figure 2

Initial memory tape contents. The negative qubit slots are used as scratch qubits and the non-negative qubit slots are initialized with interleaved program instruction and data qubits.

Figure 3

$\mathcal{Q}$ state machine diagram that corresponds to the evolution of the universal quantum computer. The overall evolution is determined by eight unitary transformations.