Quantum Circuits

One of the nicest properties of quantum computing circuits is the fact that you can achieve the same goal with a fewer number of steps compared to classical computer, and it has been a lot of fun for me to discover how to implement such algorithms.

I wanted to write about an algorithm I spent some time thinking about and wrestling with. This particular quantum circuit does not provide an improvement over a classical one (there are algorithms tacking similar problems that ac tually do provide speed-ups), but it was really nice to see how to solve a problem using quantum thinking as opposed to classical thinking.

The problem consist of coming up with an algorithm to learn the bits of a hidden string s. For this problem we restrict the string s to be a string of 0 and 1, e.g.: 100110

The classical algorithm is quite simple. It can be summarized as follows: test every bit of the string with the and operation and a 1, if the result is 1 then the bit is a 1 otherwise the bit is a 0.

To solve this problem using quantum computing I decided to break the algorithm into two parts. The first part will encode a unitary function whose main purpouse is some information from any secret string. The second part of the algorithm consists in preparing a state that represents all the possible states of a binary string s of size n. The first part of the algorith is called an oracle.

The oracle

As mentioned before, the first part of the problems boils down to finding a quantum circuit that can be used to extract information from any string s. By doing some exploration and due to previous experinece I had on similar problems I settled on the oracle that is would basically calculate the sum mod 2 of $x_i$ * $s_i$ where $x_i$ is the ith bit of an arbitrary string x and $s_i$ is the ith bit of the hidden string s. Or in other words:

$$(\sum_{i=0}^{n}s_i * x_i)\ mod\ 2$$

The above is equivalent to calculating the parity of s when x equals to 111...1. Next, then is the problem of coming up with an algorithm that encodes the above unitary, here I did testing of different circuits looking for patterns, starting with smaller strings allowed me to find patters in the circuits. For example the circuit for the string 101 looks like this:

The pattern I found was basically CNOTing all the 1 bits of the secret string. Thus, I coded up a function whose input is an arbitrary string s and the output is a quantum circuit that encodes the above unitary for the input string s. The width of the circuit varies grows linearly with the length of s(which is not great), and the number of gates grows linearly with the number of 1 in s, they are all CNOT gates which is implemented in most quantum hardware. Further there are no operations between the input qubits, only between the inputs and output qubit.

The search circuit

The world of quantum computing revolves around designing a circuit that creates an interesting superposition state, that can later be exploited to process a particular computation. One common technique to do is to create the super position where all possible states in a quantum register have equal measuring probability, this state is called the uniform superposition. For example in a 2 qubit register the uniform super position would be the state:

$$\psi = \frac{1}{4}(|00> + |01> + |10> + |11>)$$

More generally the uniform super position of an n-qubit register is:

$$\psi = \frac{1}{\sqrt{2^n}}\sum_{0}^{2^n-1}|x>$$

Such a circuit can be created via hadamard gates applied to each of the input qubits for a quantum register set to 0

The final circuit

By combining both parts we get the final circuit.

At the end of the circuit we apply hadamards to finalize the search circuit and read the measurement to classical bits.

The circuit is initialized with the state |0> plus an ancilla qubit set to |1> which helps us encode the oracle unitary and the uniform superposition. Notice the circuit labelled search circ is actually built for the hidden string s and it varies depending on s.

Finally when running the circuit we should expect to read back the hidden string s in the classical bits. Interestingly we only need to run this circuit one time to properly discover the string s. Recall the classical algorithm needs to iterate through each of the bits in the string s in order to discover s.

For the complete code, feel free to look at this repository which contains a runnable notebook you can play with.