Quantum computing

`This page is under construction`

This page is a tutorial to perform (simulated) quantum computing in in Fōrmulæ.

Fōrmulæ has a quantum computing package, in this section you will learn how to use it.

Introduction

Deterministic algorithms

Most algorithms are deterministic. It means that they follow a precise and well defined set of steps. If a given input is introduced to a deterministic program multiple times, it will always perform exactly the same set of instructions, and it will always generate the same output.

Probabilistic algorithms

There are several kinds of non-deterministic algorithms. The flavor we are interested in is named probabilistic algorithms.

Suppose we have to calculate the area of the following shape:

Since it is a irregular shape, we cannot use the well known formulae for regular shares, such as circles, polygons, etc.

One form of calculation consists in drawing a square around the shape, and select a number of randomly chosen points inside the square, such as follows:

Several points lie in the blue area, while several others do not. Lets calculate the reason of the points that lie in the blue area respect of the total of point. The area of the blue shape is approximately such that reason multiplied by the area of the enclosing square.

Of course it is an approximation, but this approximation is closed to the real area as we use more points:

It is an example of a probabilistic algorithm. Because it uses random numbers, results can differ even if we use the same input (the same shape, the same number of points, the same enclosing square) several times.

There are several probabilistic algorithms, the Monte Carlo method is a good example.

In XXXX, XXX showed a probabilistic algorithm that runs faster that any known deterministic algorithm.

Quantum mechanics

we do not pretend to explain all the theory about quantum mechanics, we only discuss the concepts that we are going to use, using (hopefully) simple examples.

You have surely known about the Schrödinger's cat paradox: There is a closed box, containing a cat and a mechanism that, after a specific period of time (let us say, an hour), with a 50% probability, will break a poison killing the cat. Quantum mechanics states that after an hour, if we do not open the box to see the result, inside the box there is a ghostly, mixed state of both alive and dead cat. The name of this phenomena is quantum superposition.

Once we decide to open the box and observe, the quantum superposition collapses to a state of alive cat or dead cat.

A superposition state can be linked, for example, suppose that, before the box experiment we have opened a hole to the box, and attached to it a video camera objective to record the activity inside the box. Then we perform the experiment. after an hour, we take the cassette or memory from the video camera (without detaching it from the box, and without opening the box). According to quantum mechanics the cassette or memory does not contain an alive or dead cat recording, but a superposition of both. The superposition of the box is linked to the videotape superposition. This phenomena is called quantum entanglement.

If we perform an observation on a superposition state, it will not only collapse to a defined state, it will also collapse all their entangles states to a consistent state. In our example, if we decide to watch the cassette or memory, it will collapse and we will see recording of either alive or dead cat. if we later open the box, we will see the same result that the recording.

Quantum computing

In order to differentiate terms, we use the term classic to refer to the traditional theories, so is common to say classic computer to a traditional computer, or quantum algorithm to refer to an algorithm that use quantum elements.

In classic computers, the minimal unit of information is a bit. It is able to store a value of either a 0 (zero) or a 1.

In quantum computers, the minimal unit of information is a qubit (a quantum bit). It is able to store a zero value, usually represented as , a 1 value, usually represented as , or a superposition of both states. More specifically, a qubit has an associated probability. What is this probability referred to ? It is the probability of the qubit to collapse to 1 once it is observed (or measured). So, a qubit with a probability of 0% will always collapse to 0 when observed, a qubit with a probability of 100% will always collapse to 1 when observed, a qubit with a probability of 25% will collapse to 0 at 1/4 oft times and to 1 75% of times when observed.

So, when qubits collapse, they become classical bits, in the same way that once we perform an Schrödinger's cat and make an observation, it collapses to a well defines state (an alive cat, or a dead cat) and the superposition disappears forever.

We can also create entangled qubits. Once we measure a qubit it collapse to be a classic bit, and their entangled qubits also collapse to be classical bits, in a consistent state.

Construction of actual bits and qubits

Bits and qubits are abstractions, in order to perform actual classical/quantum computation, physical realization of bits/qubits need to be physically built.

physical realization of bits are usually done with semiconductors.

Realization of qubits is not easy and it is currently in development stages, several materials are being tested. The main problems are the isolation of element in order to impede the interaction with other materials, and the effect of spontaneous collapse of superposition quantum states. At the time of writing this article, quantum computers are very expensive and they exist in very specialized laboratories.

What can quantum computing be used for ?

On XXXX, XXX proved that quantum computers can perform any task that classical computers can. Further, it was proved that using a quantum computer to perform a deterministic algorithm will not be faster than with a classical computer.

However, probabilistic algorithms are the land where quantum computing can grow and flourish. After all, qubits work probabilistically, as probabilistic algorithms do.

Quantum oracles

Because quantum computing has no advantage on deterministic algorithms, the usual form of solve a problem is to separate the deterministic part of it, and run it with a classical computer, cheap and accessible, and let the probabilistic part to be done with a quantum computer. This scheme is called an hybrid architecture. In this architecture, the quantum computer is usually named a quantum oracle.

Since the probabilistic part called multiple times (such as the calculation area example), usually the classical part is for preparation and the loop of the quantum oracle invocation, so the invocation is performed a lot of times.

Current model of quantum computing

How is specified the task to be performed by an quantum oracle ?

It is defined as required by the current model of quantum computation: by a quantum circuit.

The following is an example of a quantum circuit:

We can observe:

• The circuit is like a logic circuit, it consist of one or several wires. In quantum circuits they are not wires, they represent the timeline, from left to right of a qubit. It is also called qubit evolution.
• The initial values of the qubits are at the left
• The circuit contains quantum gates, that alter the nature of a qubit, or let two or more qubits to interact with each other.
• At the end of the circuit, there are measurement operations. If no measure is explicit given, an implicit measure is at the end.
• The measure of all the qubits of the circuit is retrieved to the quantum oracle's caller.

Simulation of quantum computers

Quantum computers are expensive at the moment of writing this, so simulating them is a good option.

Simulation of a quantum computer requires much calculation. The amount of operations grows exponentially of the size of the quantum circuit (number of qubits) and the number of quantum gates on it.

On the other hand, simulating (relatively small) quantum circuits are good for learning, teaching and experimentation.

Quantum computing in Fōrmulæ

Creation of quantum circuits and gates

Creation of a quantum circuit

To create a quantum circuit, select the expression Programming.Quantum.Circuit. Because the number of qubits is required, it will be asked for:

After entering the number, the circuit is like the following:

The vertical rectangle is a placeholder for quantum gates. You can add more placeholders as you wish by using the INS key:

The following quantum gates can be added to a quantum circuit:

Quantum gate Number of qubits it operates on Visual representation
Pauli X (or NOT) 1
Pauli Y 1
Pauli Z 1
Square root of NOT 1
Phase shift 1
S 1
T 1
Swap 2
Controlling 2
Measurement[note 1] 1
1. The measurement operation is not a quantum gate, but structurally it is taken as it were.

Speaking in expressions, a quantum circuit is an expression containing quantum gates as its subexpressions. For example, the following quantum circuit:

In expressions is:

Notice that qubits are numbered downwards, so the first qubit is the topmost, and that its position is 1, not 0.

Controlled gates

There are several other quantum gates, but they can be created under a special kind of gate, a controlled quantum gate. A controlled gate is when a quantum gate (such like the ones we have discussed right now) called the controlled gate works depending on the state of a specific qubit, called the controlling gate.

As expressions, a a quantum controlling gate is an expression that contains one subexpression: the controlled gate.

Because a controlling gate can contain any kind of gate (excluding a measurement), it can also contain another controlling gate, so it is possible to create a gate consisting of multiple controlling gates in cascade.

See the following examples:

Gate Visual representation Expression representation
Controlled NOT (also CNOT)
Toffoli (also CCNOT)
Fredkin (also CSWAP)

Execution of a quantum circuit

To invoke the quantum oracle, we use the Quantum.Programming.ExecuteCircuit expression. It has the following characteristics:

• It takes as parameters, the quantum circuit and an array of the input qubits.
• If the circuit contains any qubit wire containing no measurement operator, it is considered as it had an implicit one at the end (right). It means that every qubit will be eventually (explicitely or implicitely) measured.
• It returns an array of bits (no qubits, because of the last point, all the qubits will be measured).

The simplest quantum circuit is a 1-qubit circuit with no gates. Let us use as input the qubit :

Remeber that if a qubit wire does not contain a measurement operator, it contains an implicit one at the end, so (from the point of view of the ExecuteCircuit expression) the circuit is equivalent to:

So the qubit is immediately measured. Because any qubit, when measured will collapse to a 0-bit or a 1-bit, and this qubit has an associated probability to collapse to 1-bit of 0%, it will necessarily collapse to the 0-bit, which is the result retrieved.

It is common to invoke the quantum oracle many times.

Let us create a function that takes a circuit, the input qubits, and a number of calls. It will return a chart of the results:

Let us use our function with the previous example, using 100 calls:

Even if we call the quantum oracle many times, we always get a 0-bit, because all the times we have a qubit with 0% of probability to collapse to a 1-bit.

Now, we can use more complex circuits. Let us start making a simple change, We can introduce a NOT gate. This gate will change the probability of the input qubit from 0% to 100% (to collapse to a 1-bit). The result, of course, will be always a 1-bit.

Creating a superposition

The Hadamard quantum gate is the most used gate to create a superposition. It will change the probability of 0% of a qubit , or the probability of 100% from a qubit  to 50%. This is now a qubit with a superposition between the states qubit  and qubit . It means that such that qubit, once measured, approximately the half of times will collapse to a 0-bit, and the other half of times will collapse to a 1-bit:

This is an example. If the exercise would be run again we may get 50-50, of 51-49, because it is now a probabilistic program.

Creating independent qubits

Let us examine the following excercise, which uses a two-qubit circuit: