Programmable Networks for Quantum Algorithms

The implementation of a quantum computer requires the realization of a large number of $N$-qubit unitary operations which represent the possible oracles or which are part of the quantum algorithm. Until now there have been no standard ways to uniformly generate whole classes of $N$-qubit gates. We develop a method to generate arbitrary controlled phase-shift operations with a single network of one-qubit and two-qubit operations. This kind of network can be adapted to various physical implementations of quantum computing and is suitable to realize the Deutsch-Jozsa algorithm as well as Grover’s search algorithm.

Figure 1

Phase-shifting network for two qubits. The first two $z$ rotations change only the phase of the input state $|x_1,x_2⟩$: the gate on the $x_1$ line shifts the phase of the input state by $-{\varphi }_{10}/2$ if $x_1=0$ or by $+{\varphi }_{10}/2$ if $x_1=1$. The gate acts correspondingly on $x_2$. The first cnot gate generates the state $|x_1,x_1\oplus x_2⟩$ without further changing the phase. The line $x_2$ contains now the result of $x_1\oplus x_2$ (where $\oplus$ is the addition modulo $2$). Subsequent application of on this line results in a conditional shift of the phase by $-{\varphi }_{11}/2$ if $x_1\oplus x_2=0$ or by ${\varphi }_{11}/2$ if $x_1\oplus x_2=1$. The second cnot restores the state $|x_1,x_2⟩$ so that the input state is left unchanged apart from a phase shift that depends on the value of $x_1$, $x_2$, and $x_1\oplus x_2$.

Figure 2

Recursive extension of the network. By a SWAP with the $N+1$st qubit the phase shift ${\varphi }_{{\mathbf{y}}_{\mathbf{1}}\mathbf{\dots }{\mathbf{y}}_{\mathbf{N}}}\to {\varphi }_{{\mathbf{y}}_{\mathbf{1}}\mathbf{\dots }{\mathbf{y}}_{\mathbf{N}}\mathbf{0}}$ (controlled by the original condition) appears now on the $N+1$st qubit. A second SWAP and a subsequent cnot from the $N$th to the $N+1$st qubit give the original condition XORed with $x_{N+1}$—this condition controls the second $z$ rotation. We mention the identity .

Figure 3

The three-bit network for a system with nearest-neighbor $XY$ coupling. The dashed lines indicate the parts of the two-bit network which have been replaced according to rule (ii).

Figure 4

Optimized four-bit network for qubits with nearest-neighbor $XY$ coupling. With this network (plus the Hadamard gate for each qubit), both the Deutsch-Jozsa algorithm and database search can be realized, e.g., with Josephson charge qubits. We have assumed qubits coupled in a chain with periodic boundary conditions. A particularly interesting feature of this network is that nearest-neighbor coupling allows for parallel execution of operations. Note that the $z$ rotations and the two-qubit operations appear in well-separated blocks. The optimization criterion here was to minimize the number of two-qubit blocks.