A sample quantum algorithm, useful for demonstrating languages

Question

I'm looking for a quantum algorithm which I can use to demonstrate the syntax of different quantum-languages. My question is similar to this, however, for me, "good" means:

• What it does could be described in 1-2 paragraphs, and should be easy to understand.
• Should use more elements of the "quantum-programming-world" (I mean that the algorithm should use some classical constants, measurements, conditions, qregisters, operators etc., as many as possible).
• The algorithm should be small (at most 15-25 pseudocode-lines long).

Useful algorithms are often too long/hard, but Deutsch's algorithm doesn't use that many elements. Can someone suggest me a good-for-demo algorithm?

Answer 1

I suggest looking at eigenvalue/eigenvector estimating protocols. There's a lot of flexibility to make the problem as easy or as hard as you want.

Start by picking two parameters, $n$ and $k$. You want to design an $n$-qubit unitary, $U$ that has eigenvalues of the form $e^{-2\pi iq/2^k}$ for integers $q$. Make sure that at least one of those eigenvalues is unique, and call it $\omega$. Also make sure that a simple product state, say $|0\rangle^{\otimes n}$, has non-zero overlap with the eigenvector of eigenvalue $\omega$.

The aim would be to implement a phase estimation algorithm on this, being told the value $k$, and being tasked with outputting a vector $|\psi\rangle$ that is the eigenvector corresponding to eigenvalue $\omega$. In general this will comprise a circuit of $n+k$ qubits (unless you need ancillas to implement controlled-$U$).

This works as follows:

• set up two registers, one of $k$ qubits, and the other of $n$ qubits. (use of quantum registers)

• every qubit is initialized in the state $|0\rangle$. (initialisation of quantum registers)

• apply a Hadamard to each qubit in the first register (single-qubit gates)

• from qubit $r$ in the first register, apply controlled-$U^{2^{r}}$, targeting the second register (multi-qubit controlled gates)

• apply the inverse Fourier transform on the first register, and measure every qubit of the first register in the standard basis. These can be combined, implementing the semi-classical Fourier transform. (measurement and feed-forward of classical data)

• for the correct measurement result, the second register is in the desired state $|\psi\rangle$.

For simplicity, you could pick $n=2$, $k=1$, so you need a $4\times 4$ unitary matrix with eigenvalues $\pm 1$. I'd use something like $$(U_1\otimes U_2)C(U_1^\dagger\otimes U_2^\dagger),$$ where $C$ denotes the controlled-NOT. There is just one eigenvector with eigenvalue -1, which is $|\psi\rangle=(U_1\otimes U_2)|1\rangle\otimes(|0\rangle-|1\rangle)/\sqrt{2}$, and you can mess about with the choices of $U_1$ and $U_2$ to explore the implementation of $U$ using decomposition in terms of a universal gate set (I'd probably set this as a preliminary problem). Then, controlled-$U$ is easily implemented just by replacing the controlled-NOT with a controlled-controlled-NOT (Toffoli) gate. Finally, the inverse Fourier transform is just a Hadamard gate.

For something a little more complex, put $k=3$, and replace $C$ with the square-root of swap gate, $$ \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 0 & \frac{1}{\sqrt{2}} & \frac{i}{\sqrt{2}} & 0 \\ 0 & \frac{i}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right) $$ with $\omega=e^{\pm i\pi/4}$ and $|\psi\rangle=(U_1\otimes U_2)(|01\rangle\pm|10\rangle)/\sqrt{2}$.

Answer 2

Sounds like you want a quantum "Hello World". The most straightforward quantum version of this would just be to write a binary encoded version of the text Hello World in a register of qubits. But this would require ~100 qubits, and be longer than your upper limit for code length.

So let's write a shorter peice of text. Let's write ;), we need a bit string of length 16. Specifically, using ASCII encoding

;)  =  00111011 00101001

Using QISKit, you'd do this using the following code.

from qiskit import QuantumProgram
import Qconfig

qp = QuantumProgram()
qp.set_api(Qconfig.APItoken, Qconfig.config["url"]) # set the APIToken and API url

# set up registers and program
qr = qp.create_quantum_register('qr', 16)
cr = qp.create_classical_register('cr', 16)
qc = qp.create_circuit('smiley_writer', [qr], [cr])

# rightmost eight (qu)bits have ')' = 00101001
qc.x(qr[0])
qc.x(qr[3])
qc.x(qr[5])

# second eight (qu)bits have 00111011
# these differ only on the rightmost two bits
qc.x(qr[9])
qc.x(qr[8])
qc.x(qr[11])
qc.x(qr[12])
qc.x(qr[13])

# measure
for j in range(16):
    qc.measure(qr[j], cr[j])

# run and get results
results = qp.execute(["smiley_writer"], backend='ibmqx5', shots=1024)
stats = results.get_counts("smiley_writer")

Of course, this isn't very quantum. So you could do a superposition of two different emoticons instead. The easiest example is to superpose ;) with 8), since the bit strings for these differ only on qubits 8 and 9.

;)  =  00111011 00101001
8)  =  00111000 00101001

So you can simply replace the lines

qc.x(qr[9])
qc.x(qr[8])

from the above with

qc.h(qr[9]) # create superposition on 9
qc.cx(qr[9],qr[8]) # spread it to 8 with a cnot

The Hadamard creates a superposition of 0 and 1, and the cnot makes it into a superposition of 00 and 11 on two qubits. This is the only required superposition for ;) and 8).

If you want to see an actual implementation of this, it can be found on the QISKit tutorial (full disclosure: it was written by me).

Answer 3

I would propose the (perfect) 1-bit random number generator. It is almost trivially easy:

You start with a single qubit in the usual initial state $\left|0\right>$. Then you apply the Hadamard gate $H$ which produces the equal superposition of $\left|0\right>$ and $\left|1\right>$. Finally, you measure this qubit to get either 0 or 1, each with 50% probability.