# A sample quantum algorithm, useful for demonstrating languages

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?

• Is your requirement also that it should be an "algorithm" with a classical input and classical output, and a clear benefit/difference from the way the equivalent classical algorithm would work? Commented Apr 11, 2018 at 10:55
• @DaftWullie These are not required. An operator's paramter or classican constant initialization can represent the "input" for me, and I'll provide the output format if needed. It doesn't need to do/be special. The focus is on the languages' syntax, the description is only for validating that the codes in different languages are the same. The meaning of the algorithm is irrelevant. Commented Apr 11, 2018 at 11:25
• Welcome to Quantum Computing SE! Just to check, is your criteria for a good answer the most elements in the shortest pseudo code? Commented Apr 11, 2018 at 12:38
• @Mithrandir24601 Thanks! Yes, somehow like that. Commented Apr 11, 2018 at 12:51

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}$.

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).

• I get 404 for that link. Did you move the file elsewhere? Commented Apr 21, 2018 at 13:50
• It seems the tutorial was just updated. I changed the link, so it should work now. Commented Apr 21, 2018 at 15:30

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.