Quantum computing

From Fōrmulæ wiki
Revision as of 20:37, 24 March 2020 by Admin (Talk | contribs) (Probabilistic algorithms)

Jump to: navigation, search
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:

QuantumTutorial01.png

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:

QuantumTutorial02.png

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 the mid 1970s, Robert Solovay and Volker Strassen found a probabilistic algorithm to test if a number is prime or composite and proved that it runs faster that any known deterministic algorithm.Cite error: Closing </ref> missing for <ref> tag || QuantumTutorial08.png |- | Pauli Y || Programming.Quantum.Gate.PauliY || The index of qubit in the circuit[note 1] || QuantumTutorial09.png |- | Pauli Z || Programming.Quantum.Gate.PauliZ || The index of qubit in the circuit[note 1] || QuantumTutorial10.png |- | Hadamard || Programming.Quantum.Gate.Hadamard || The index of qubit in the circuit[note 1] || QuantumTutorial11.png |- | Square root of NOT || Programming.Quantum.Gate.SqrtNot || The index of qubit in the circuit[note 1] || QuantumTutorial12.png |- | Phase shift || Programming.Quantum.Gate.PhaseShift || The index of qubit in the circuit[note 1]
The value of the numerator[note 2]
The value of the denominator[note 2] || QuantumTutorial13.png |- | S || Programming.Quantum.Gate.S || The index of qubit in the circuit[note 1] || QuantumTutorial14.png |- | T || Programming.Quantum.Gate.T || The index of qubit in the circuit[note 1] || QuantumTutorial15.png |- | Swap || Programming.Quantum.Gate.Swap || The indexes of the swapping qubits in the circuit[note 1] || QuantumTutorial16.png |- | Controlling || Programming.Quantum.Gate.Controlling || The index of the controlling qubit in the circuit[note 1]
The controlled gate[note 3] || QuantumTutorial17.png |- | Measurement[note 4] || Programming.Quantum.Measurement || The index of qubit in the circuit[note 1] || QuantumTutorial18.png |}

  1. Cite error: Invalid <ref> tag; no text was provided for refs named x
  2. 2.0 2.1 The result is a phase shift of .
  3. The controlled gate is given as the unique child expression of the controlling expression.
  4. 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:

QuantumTutorial20.png

In expressions is:

QuantumTutorial21.png

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) QuantumTutorial30.png QuantumTutorial31.png
Toffoli (also CCNOT) QuantumTutorial32.png QuantumTutorial33.png
Fredkin (also CSWAP) QuantumTutorial34.png QuantumTutorial35.png

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 :

QuantumTutorial40.png

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:

QuantumTutorial41.png

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:

QuantumTutorial42.png

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

QuantumTutorial43.png

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.

QuantumTutorial44.png

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 if we had several qubits in such that state, and they all were measured, approximately the half of them would collapse to a 0-bit, and the other half would collapse to a 1-bit:

QuantumTutorial45.png

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 in superposition

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

QuantumTutorial46.png

The first bit will be 0-bit or 1-bit, with 50% probability each, and the second bit will always be 0-bit. So, the two possible result are "00" and "10", with equal probability each.

In the following example, the two qubits are in superposition state, but they are independent of each other, so the four possible results are "00", "01", "10" and "11" with equal (25%) probability each.

QuantumTutorial47.png

Creating entangled qubits

The minimal circuit to produce an entanglement of qubits is the following:

QuantumTutorial48.png

The CNOT (controlled not) gate is a conditional not gate, it makes the following: If the controlling qubit (in this case, the first one) is , then it flips (NOT) the content of the controlled (or target) qubit (in this case, the second one), elsewere it does nothing.

But wait, how the controlled-not gate could know if the first qubit is if it is in a superposition state between and  ? It does not, the second qubit is left also in a superposition state. Do you remember the Schrödinger's cat paradox at the start of this document ? To make an analogy, the first qubis is the box, and the second qubit is the video camera recorder.

The two qubits are in a superposition state but their states are correlated (entangled). After a measurement of the first qubit, if it were the 0-bit, the second qubit would remain unchanged (0). If the first qubit were measured as the 1-bit, the controlled gate would flip the content of the second qubit from 0 to 1. In both cases we can only get two and only two results "00" and "11" with 50% probability each, as you saw in the previous figure.

The same result must be obtained if we measured the second qubit first. after such that measurement, any measurement of the first qubit will always report the same value from the second one.

Notice that entanglement does not mean that entangled qubits will always collapse the the same value after any measure (it is for the previous example). It means that the results will always be consistent. For example, see the following figure. It is the same as the previous one, except that the second qubit is initialized as . Now, the two qubits will always have the opposite value after any measurement:

QuantumTutorial49.png

Examples of quantum programs

In this section, several (very simple) programs will be written as quantum programs.

Two simple and very known problems of classical computation will be solved in quantum form.

As shown before, the using of quantum computing for solving classical (deterministic) problems offers no advantage. However, we are doing this for educational purposes. after all, we are using a simulated quantum oracle, not a real one, so we are not wasting expensive resources.

Introduction

In electronics and (classical) digital circuits theories, is a very common exercise to design adders. An adder is a digital circuit used to sum bits. An adder of two bits are named a half adder. An adder for three bits is called a full adder.

A half adder

Classically, a half adder is created with the following digital circuit:

QuantumTutorial50 0.png

This circuit has the following tables of inputs and outputs:

Inputs Outputs
A B C S
0 0 0 0
1 0 0 1
0 1 0 1
1 1 1 0

There are several quantum circuits able to create a half adder. Maybe the simplest one is:

QuantumTutorial50.png

Input bits are A and B, giving the sum S with carry out C.

We will need a function to convert bits to qubits, this is, if the input of this function is the bit 0 or 1, it return the qubit or respectively:

QuantumTutorial51.png

he following is the program for the half adder:

QuantumTutorial52.png

To test the program, we calculate all the possible combinations of two input bits. Notice that the result is in decimal.

QuantumTutorial53.png

A full adder

Classically, a full adder is created with the following digital circuit:

QuantumTutorial50 0b.png

This circuit has the following tables of inputs and outputs:

Inputs Outputs
A B Cin Cout S
0 0 0 0 0
0 0 1 0 1
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 1

There are several quantum circuits able to create a full adder. Maybe the simplest one is:

QuantumTutorial50a.png

Input bits are A, B and Cin, giving the sum S with carry out C.

he following is the program for the full adder:

QuantumTutorial52b.png

To test the program, we calculate all the possible combinations of three input bits. Notice that the result is in decimal.

QuantumTutorial53b.png

Programmatic creation of quantum circuits and gates

Up now, we have created quantum circuits and gates manually. However, it is possible to create them by programming. see the following example:

QuantumTutorial60.png

The Shor's algorithm is a very well known probabilistic quantum algorithm, for integer factorization. This algorithm requires to apply the called quantum Fourier transform to the input. The interesting part is that this transform is a quantum circuit which depends of the input. It means that for every input has its own quantum circuit!

The following program generates the quantum circuit for the discrete Fourier transform, which depends of the input n:

QuantumTutorial61.png

The following are some result, for n 1..5: (Note. Several authors define the circuit slightly different).

QuantumTutorial62.png

Inspecting the mathematics behind quantum computing

There are mathematical concepts that govern the evolution of qubits through a quantum circuit. In this part we do not pretend to explain it to detail.

The evolution of the qubits on a single gate are defined as a unitary matrix of complex numbers, which can in turn be defined as operations (usually tensor products).

The complete circuit can be represented as a the multiplication of such these matrices.

A quantum circuit with n qubits and m quantum gates, are defined as a 2n x 2n matrix of complex numbers, which is also (at least) a multiplication of m 2n x 2n matrices.

As you can see, the matrices grow exponentially to the number of qubits. This growing makes the simulation of quantum circuit possible for relatively few qubits only.

For an example, consider the following 3-qubit circuit, with associated matrices of size 23 x 23 = 8 x 8:

QuantumTutorial70.png

The expression Programming.Circuit.GetCircuitMatrix retrieves the associated matrix of the circuit:

QuantumTutorial72.png

Because Fōrmulæ is a symbolic system, it is able to provide the result symbolically. Most quantum programming languages are able to manage the calculations numerically.

The expression Programming.Circuit.GetCircuitOperations retrieves the associated matrix of the circuit, as a multiplication of matrices, representing each every gate of the circuit):

QuantumTutorial71.png

Both the expression Programming.Circuit.GetCircuitMatrix and Programming.Circuit.GetCircuitOperations can only accept quantum circuit containing no measurement operations.