Greedy algorithm python – Coin change problem

A greedy python algorithm (greedy algorithm python) greedily selects the best choice at every step. He hopes that these choices lead to the optimal overall solution to the problem. So, a greedy algorithm does not always give the best solution. However in many problems this is the case.

A greedy python algorithm (greedy algorithm python) greedily selects the best choice at every step. He hopes that these choices lead to the optimal overall solution to the problem. So, a greedy algorithm does not always give the best solution. However in many problems this is the case.

Greedy Algorithm: Introduction

The problem of giving change is formulated as follows. How to return a given sum with a minimum of coins and banknotes?

Here is an example in python of the resolution of the problem:

If we consider the Euro monetary system without the cents we have the whole

EURO = (1, 2, 5, 10, 20, 50, 100, 200, 500)

Greedy algorithm python : Coin change problem

Now, to give change to an x ​​value of using these coins and banknotes, then we will check the first element in the array. And if it’s greater than x, we move on to the next element. Otherwise let’s keep it. Now, after taking a valuable coin or bill from the array of coinAndBill [i], the total value x we ​​need to do will become x – coinAndBill [i].

Here is the associated greedy python algorithm:

def renduMonnaieGlouton(x):
  pieceEtBillets = [500,200,100,50,20,10,5,2,1]
  i = 0

  while(x>0):
    if(pieceEtBillets[i] > x):
      i = i+1
    else:
      print(str(pieceEtBillets[i]))
      x -= pieceEtBillets[i];

renduMonnaieGlouton(33)#Exemple sur 33 euros

The output for 33 euro is then:

20
10
2
1

Another example with 55 euro of greedy python algorithm:

def renduMonnaieGlouton(x):
  pieceEtBillets = [500,200,100,50,20,10,5,2,1]
  i = 0

  while(x>0):
    if(pieceEtBillets[i] > x):
      i = i+1
    else:
      print(str(pieceEtBillets[i]))
      x -= pieceEtBillets[i];

renduMonnaieGlouton(55)#Exemple sur 55 euros

Output :

50
5

Conclusion

The problem of giving change is NP-difficult relative to the number of coins and notes of the monetary system considered (euro in this example). To go further, we can demonstrate that for certain so-called canonical money systems, the use of a greedy algorithm is optimal. A monetary system is said to be canonical if for any sum s the greedy algorithm leads to a minimal decomposition.

NP difficulty is the defining property of a class of problems informally “at least as difficult as the most difficult NP problems”.

A simple example of an NP-hard problem is the sum of subset problem. If P is different from NP then it is unlikely to find a polynomial time algorithm that exactly solves this problem.

External links :

http://math.univ-lyon1.fr/irem/IMG/pdf/monnaie.pdf

http://www.dil.univ-mrs.fr/~gcolas/algo-licence/slides/gloutons.pdf

Internal links python greedy algorithm :

http://128mots.com/index.php/category/python/

http://128mots.com/index.php/category/non-classe/

Levenshtein Python Algo implementation Wagner & Fischer

Here is the levenshtein python implementation of the Wagner & Fischer algorithm (Wagner-Fischer). It allows to calculate the distance of Levenshtein (distance between two strings of characters).

Here is the python implementation of the Wagner & Fischer algorithm (Wagner-Fischer). It allows to calculate the distance of Levenshtein (distance between two strings of characters).

First, the goal of the algorithm is to find the minimum cost. Minimal cost to transform one channel into another. Then a recursive function allows to return the minimum number of transformation. And to transform a substring of A with n characters into a substring of B with the same number of characters. The solution is given. We must calculate the distance between the 2 letters at the same position in the chain A and B. Then Either the letters and the previous letter are identical. Either there is a difference and in this case we calculate 3 costs. So the first is to delete a letter from the chain A. And insert a letter in the chain A to substitute a letter from the chain A. Then we can then find the minimum cost.

Example of levenshtein python implementation :

import numpy as np

def levenshtein(chaine1, chaine2):
    taille_chaine1 = len(chaine1) + 1
    taille_chaine2 = len(chaine2) + 1
    levenshtein_matrix = np.zeros ((taille_chaine1, taille_chaine2))
    for x in range(taille_chaine1):
        levenshtein_matrix [x, 0] = x
    for y in range(taille_chaine2):
        levenshtein_matrix [0, y] = y

    for x in range(1, taille_chaine1):
        for y in range(1, taille_chaine2):
            if chaine1[x-1] == chaine2[y-1]:
                levenshtein_matrix [x,y] = min(
                    levenshtein_matrix[x-1, y] + 1,
                    levenshtein_matrix[x-1, y-1],
                    levenshtein_matrix[x, y-1] + 1
                )
            else:
                levenshtein_matrix [x,y] = min(
                    levenshtein_matrix[x-1,y] + 1,
                    levenshtein_matrix[x-1,y-1] + 1,
                    levenshtein_matrix[x,y-1] + 1
                )
    return (levenshtein_matrix[taille_chaine1 - 1, taille_chaine2 - 1])

print("distance de levenshtein = " + str(levenshtein("Lorem ipsum dolor sit amet", "Laram zpsam dilir siy amot")))

To calculate the Levenshtein distance with a non-recursive algorithm. We use a matrix which contains the Levenshtein distances. Then These are the distances between all the prefixes of the first string and all the prefixes of the second string.

Also we can dynamically calculate the values ​​in this matrix. The last calculated value will be the Levenshtein distance between the two whole chains.

Finally there are many use cases of the Levenshtein distance. Levenshtein distance is used in domains. Computational linguistics, molecular biology. And again bioinformatics, machine learning. Also deep learning, DNA analysis. In addition, a program that does spell checking uses, for example, the Levenshtein distance.

Links on the Wagner & Fischer algorithm (Wagner-Fischer) and the Levenshtein python distance or other language:

https://graal.hypotheses.org/tag/algorithme-de-wagner-fischer

https://fr.wikipedia.org/wiki/Algorithme_de_Wagner-Fischer

https://fr.wikipedia.org/wiki/Distance_de_Levenshtein

https://medium.com/@sddkal/wagner-fischer-algorithm-be0d96893f6d

https://www.python-course.eu/levenshtein_distance.php

Internal links on algorithms

http://128mots.com/index.php/category/python/

http://128mots.com/index.php/category/graphes/

Quantum sort : sorting algorithm IBM Qiskit tutorial python

In this article, I propose a quantum sort algorithm with Qiskit tutorial in python that allows you to sort a list of integers coded on two qubits. I have found that there is little literature on the subject. This algorithm can be used and can be used as a basis for solving sorting problems on an unsorted list of integers.

Introduction

We consider the following problem: Given a list of four integers between 0 and 3 that are strictly different sort the given list. The solution proposed is a quantum sort algorithm.

Quantum sort : sorting algorithm IBM Qiskit python IBM Qiskit tutorial
Figure 1 : Problem to solve with Quantum sorting algorithm

A classic sorting algorithm such as merge sorting solves the problem, see in more detail my article on the subject:

Merge sorting follows the divide and conquer paradigm of dividing the initial task into two similar smaller tasks.

Some concepts of quantum algorithm and IBM Qiskit tutorial

I recall here some concept that we are going to use in our quantum sorting algorithm, so I advise you to consult the IBM Qiskit site to learn more https://qiskit.org/textbook/what-is-quantum.html and also to read the very good book “Programming Quantum Computers: Essential Algorithms and Code Samples” by Eric R. Johnston, Nic Harrigan, Mercedes Gimeno-Segovia:

Circuits

The principle in quantum algorithm is to manipulate qubits for inputs which we have in outputs which we need, the process can be represented in the form of circuit (inputs on the left, output on the right). We can perform different operations by means of quantum gate (which act on the qubits in a way similar in classical algorithm to logic gates like AND, OR, Exclusive OR…).

In this article I will rely on Qiskit which is the IBM framework for quantum computing.

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi

qreg_qubit = QuantumRegister(2, 'qubit')
creg_classic = ClassicalRegister(2, 'classic')
circuit = QuantumCircuit(qreg_qubit, creg_classic)

circuit.reset(qreg_qubit[0])
circuit.reset(qreg_qubit[1])
circuit.x(qreg_qubit[0])
circuit.measure(qreg_qubit[0], creg_classic[0])
circuit.measure(qreg_qubit[1], creg_classic[1])

In this first algorithm, a quantum register is initialized to the state | 01> measures in a classical register the quantum state of a register of 2 qubits. The circuit can be drawn using the circuit.draw () instruction or via Circuit Composer from IBM Quantum Experience: https://quantum-computing.ibm.com/

Quantum sort : sorting algorithm IBM Qiskit python IBM Qiskit tutorial
Quantum state of a single qubit:

The state of a qubit can be expressed as a state vector:

    \[|q\rangle = \cos{(\tfrac{\theta}{2})}|0\rangle + e^{i\phi}\sin{\tfrac{\theta}{2}}|1\rangle\]

With alpha and beta which are complex numbers (ie a real and imaginary part) in this case there is the relation (mathematical reminder on complex numbers: https://www.mathsisfun.com/numbers/complex-numbers.html):

    \[|\psi\rangle = \alpha|0\rangle + \beta|1\rangle\]

If we go into trigonometric and exponential form we have with θ and ϕ which are real numbers.

    \[\sqrt{|\alpha|^2 + |\beta|^2} = 1\]

So if we measure a qubit q we have:

    \[|q\rangle = \alpha|0\rangle + \beta|1\rangle\]

That is, there is a probability of measuring the qubit in state | 0> and a probability of measuring the qubit in state | 1>. The measurement of a qubit reveals whether it is in state 1 or in state 0, in general the measurement is placed at the end of the circuit because it affects the state of the qubit accordingly.

Quantum gates

Here are some quantum gates to know that we will use in our quantum sorting algorithm:

Gate X (Pauli-X) :

Gate X is used to return the state of the qubit without modifying the phase:

    \[X = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = |0\rangle\langle1| + |1\rangle\langle0|\]

<

See the example above with the use of qiskit.

Gate Y (Pauli-Y) :

The pauli Y gate allows you to return the phase and the qubit at the same time:

Example if we consider here the initialized state | 0> of the qubit and its phase of 0, there is then a 100% chance of measuring the state | 0>.

Quantum sort : sorting algorithm IBM Qiskit python IBM Qiskit tutorial

Applying the quantum gate Y has the following effect on the state and phase of the qubit:

Quantum sort : sorting algorithm IBM Qiskit python IBM Qiskit tutorial

There is then a 100% chance of measuring state 1 and the phase is reversed (see the bloch sphere above)

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi

qreg_qubit = QuantumRegister(1, 'qubit')
creg_classic = ClassicalRegister(1, 'classic')
circuit = QuantumCircuit(qreg_qubit, creg_classic)

circuit.reset(qreg_qubit[0])
circuit.y(qreg_qubit[0])
circuit.measure(qreg_qubit[0], creg_classic[0])

Gate Z (Pauli-Z) :

The Z gate is used to return only the phase and not the state of the qubit.

Note that the Y and Z gates can be represented by the following matrices:

    \[Y = \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix} \quad\quad\quad\quad Z = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}\]

    \[Y = -i|0\rangle\langle1| + i|1\rangle\langle0| \quad\quad Z = |0\rangle\langle0| - |1\rangle\langle1|\]

Voir : https://qiskit.org/textbook/ch-states/single-qubit-gates.html

Hadamard Gate

The Hadamard gate (H gate) is an important quantum gate which allows to create a superposition of | 0⟩ and | 1⟩.

The matrix of this gate is:

    \[H = \tfrac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}\]

SWAP Gate

A SWAP gate allows the state of two qubits to be exchanged:

SWAP state example | 1⟩ from qubit 0 to qbit 2

IBM Qiskit tutorial

And state SWAP | 0⟩ from qubit 1 to qbit 2

Quantum sort : sorting algorithm IBM Qiskit python IBM Qiskit tutorial

In Python with the Qiskit framework we have:

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi

qreg_qubit = QuantumRegister(3, 'qubit')
creg_classic = ClassicalRegister(1, 'classic')
circuit = QuantumCircuit(qreg_qubit, creg_classic)

circuit.reset(qreg_qubit[0])
circuit.reset(qreg_qubit[1])
circuit.reset(qreg_qubit[2])
circuit.x(qreg_qubit[0])
circuit.swap(qreg_qubit[1], qreg_qubit[2])
circuit.measure(qreg_qubit[2], creg_classic[0])

Toffoli Gate

The Toffoli quantum gate is three qubits (two commands and one target).
It performs a phase reversal (quantum gate X on the target) only if both controls are in state | 1⟩.
A Toffoli is equivalent to an UNControlled gate (it is also called the CCX gate).

Example below with 2 command qubits in state | 1⟩ there is then a 100% chance of measuring the state | 1⟩ on the target qubit of the tofoli gate which was initially initialized to state | 0⟩ (or a reversal of the state).

Quantum sort : sorting algorithm IBM Qiskit python

Example below in the opposite case (there is then 0% chance of measuring state | 1⟩ or 100% chance of measuring state | 0⟩):

Quantum sort : sorting algorithm IBM Qiskit python
Classical gate AND gate, OR gate equivalence in quantum gate – IBM Qiskit tutorial

We see here how to combine doors to create a behavior equivalent to what we are used to using in classical circuits.

Gate AND :

From Qbit a and b and a qubit with a forced initialization to state | 0⟩ we can obtain the operation a AND b using a Toffoli quantum gate and a SWAP mate.

Quantum sort : sorting algorithm IBM Qiskit python
Le circuit suivant effectue un classique ET sur un algorithme quantique

It should be noted that at the end of this circuit we find the state A AND B on qubit B the state of qubit B is ultimately on qubit C.

The equivalent python code is as follows:

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi

qreg_a = QuantumRegister(1, 'a')
qreg_b = QuantumRegister(1, 'b')
qreg_c = QuantumRegister(1, 'c')
creg_aANDb = ClassicalRegister(1, 'aANDb')
creg_aState = ClassicalRegister(1, 'aState')
creg_bState = ClassicalRegister(1, 'bState')
circuit = QuantumCircuit(qreg_a, qreg_b, qreg_c, creg_aANDb, creg_aState, creg_bState)

circuit.reset(qreg_c[0])
circuit.ccx(qreg_a[0], qreg_b[0], qreg_c[0])
circuit.swap(qreg_b[0], qreg_c[0])
circuit.measure(qreg_b[0], creg_aANDb[0])
circuit.measure(qreg_a[0], creg_aState[0])
circuit.measure(qreg_c[0], creg_bState[0])

The equivalent of this code in OpenQASM assembler is:

OPENQASM 2.0;
include "qelib1.inc";

qreg a[1];
qreg b[1];
qreg c[1];
creg aANDb[1];
creg aState[1];
creg bState[1];

reset c[0];
ccx a[0],b[0],c[0];
swap b[0],c[0];
measure b[0] -> aANDb[0];
measure a[0] -> aState[0];
measure c[0] -> bState[0];

We will use this gate (in Quantum sort algorithm for example) to perform our quantum list sorting, here are some tests:

For | 0⟩ AND | 0⟩ you have | 0⟩ on qubit B:

IBM Qiskit tutorial

For | 0⟩ AND | 1⟩ you have | 0⟩ on qubit B:

IBM Qiskit tutorial

For | 1⟩ AND | 0⟩ you have | 0⟩ on qubit B:

Finally for | 1⟩ AND | 1⟩ you have good | 1⟩ on qubit B with a probability of 100%:

IBM Qiskit tutorial

Gate OR :

We will use it in Quantum sort algorithm.

To realize an OR gate we combine 4 X quantum gates, a Toffoli gate and a SWAP quantum gate, also the state of C must be initialized to the state | 1>:

IBM Qiskit tutorial

The code for this door in Qiskit:

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi

qreg_a = QuantumRegister(1, 'a')
qreg_b = QuantumRegister(1, 'b')
qreg_c = QuantumRegister(1, 'c')
creg_aORb = ClassicalRegister(1, 'aORb')
creg_aState = ClassicalRegister(1, 'aState')
creg_bState = ClassicalRegister(1, 'bState')
circuit = QuantumCircuit(qreg_a, qreg_b, qreg_c, creg_aORb, creg_aState, creg_bState)

circuit.reset(qreg_a[0])
circuit.reset(qreg_b[0])
circuit.x(qreg_b[0])
circuit.x(qreg_c[0])
circuit.x(qreg_a[0])
circuit.ccx(qreg_a[0], qreg_b[0], qreg_c[0])
circuit.x(qreg_a[0])
circuit.x(qreg_b[0])
circuit.swap(qreg_b[0], qreg_c[0])
circuit.measure(qreg_b[0], creg_aORb[0])
circuit.measure(qreg_a[0], creg_aState[0])
circuit.measure(qreg_c[0], creg_bState[0])

in OpenQASM :

OPENQASM 2.0;
include "qelib1.inc";

qreg a[1];
qreg b[1];
qreg c[1];
creg aORb[1];
creg aState[1];
creg bState[1];

reset a[0];
reset b[0];
x b[0];
x c[0];
x a[0];
ccx a[0],b[0],c[0];
x a[0];
x b[0];
swap b[0],c[0];
measure b[0] -> aORb[0];
measure a[0] -> aState[0];
measure c[0] -> bState[0];

If we test we get a OR gate :

Here for | 0⟩ OR | 0⟩ you have good | 0⟩ on qubit B with a probability of 100%:

Here for | 0⟩ OR | 1⟩ you have good | 1⟩ on qubit B with a probability of 100%:

For | 1⟩ OR | 0⟩ you have good | 1⟩ on qubit B with a probability of 100%:

Quantum sort algorithm.

Finally for | 1⟩ OR | 1⟩ you have good | 1⟩ on qubit B with a probability of 100%:

Quantum sort algorithm.

Quantum sort : Quantum sorting algorithm

Quantum sort algorithm

To solve this problem we will first create a quantum circuit (used in Quantum sort algorithm) that allows you to measure if a figure is lower than another for this the intuition is to be based on a circuit similar to a classic circuit of comparison of magnitude at 2 qubit .

Quantum magnitude comparator for Quantum sort algorithm:

We consider a digit A stored in a 2 qubit register (A0, A1) and a digit B stored in another register (B0, B1):

Link here: https://www.electronics-tutorials.ws/combination/comb_8.html

To know if A> B with 2 registers of 2 Qubits, the equation must be applied:

(A_{1}\overline{B_{1}})+((A_{1}A_{0}+A_{0}\overline{B_{1}})\overline{B_{0}})

The equivalent circuit to create this is:

Here in the example the 2 bits compared by this circuit are in register a and register B

Quantum qubit magnitude comparator

The equivalent code for this comparator in OpenQASM is:

I have created a GATE comparator4 which has the following OPENQASM equivalent code:

gate comparator4 a, b, c, d, f, g, i, j, k, l {
  x d;
  x j;
  x l;
  andG1 b, d, f;
  andG2 a, b, g;
  andG3 a, f, i;
  orG1 b, f, j;
  x c;
  andG4 c, f, k;
  x c;
  orG2 d, f, l;
  swap d, i;
  x d;
  swap b, g;
}

So we see that this custom quantum gate is made up of a quantum AND gate and a custom quantum OR gate that I created in the following way. If we unfold the doors andG1, andG2, andG3, orG1, orG2 we have:

The OpenQASM equivalent code to write the different gate andG1, andG2, andG3, orG1, orG2 to create comparator 4 is:

gate andG1 a, b, c {
  ccx a, b, c;
  swap b, c;
}

gate andG2 a, b, c {
  ccx a, b, c;
  swap b, c;
}

gate andG3 a, b, c {
  ccx a, b, c;
  swap b, c;
}

gate orG1 a, b, c {
  x a;
  x b;
  ccx a, b, c;
  x a;
  x b;
  swap b, c;
}

gate andG4 a, b, c {
  ccx a, b, c;
  swap b, c;
}

gate orG2 a, b, c {
  x a;
  x b;
  ccx a, b, c;
  x a;
  x b;
  swap b, c;
}
Circuit for checking a sorted list

If we consider here a list of 4 digits stored in the 4 registers of 2 qubits: a, b, m, n. The circuit above is used to test whether the input list is sorted or not. For this I cascaded 3 quantum magnitude comparators (seen in detail in the previous paragraph). Thus the circuit obtained will test if a> b and put the result on the qbit c then check if b> m and store the result on the qbit o and finally it tests if m> n and store the result on the qubit q.

The last quantum gate andOnCompare makes it possible to apply a mutliple AND part: if c AND o AND q are in the quantum state | 1> then the qubit q is set in the quantum state | 1> otherwise it is in the quantum | 0>:

Below is the code of the door andOnCompare in openQASM:

gate andOnCompare a, b, c, d, f {
  ccx a, b, d;
  swap b, d;
  ccx b, c, f;
  swap c, f;
}

We have thus created a verification circuit that a list of 4 digits stored in registers a, b, m, n is sorted in a decreasing way or not. The result is stored in the qubit q which has a 100% chance of being measured at state | 1> if the list is sorted otherwise 100% to be at | 0> if the list a, b, m, n is not in decreasing order.

In the general diagram above we notice that in the example:

a=0,b=2,m=3,n=1

in this case this circuit will return the quantum state | 0> on the qubit q

Creation of a circuit of permutations

The idea of ​​our algorithm is to permute these 4 digits using control qubits which will be in superimposed state.

The permutation circuit is as follows:

A register of 6 Qubit “control” allows to control the permutation of the list knowing that there are for 4 elements: 4 * 3 * 2 * 1 possible permutations that is to say 24 possibilities the 6 qubits allow to generate these different states.

4 Hadamard quantum gates are used to implement these permutations and take advantage of the superposition of the Qubit ‘control’ register

In other words in the circuit above we see that we start the circuit by initializing the registers a, b, m, n with its list of unsorted numbers, here (a = 0, b = 2, m = 3, n = 1).

The permutation circuit which is controlled by a superimposed qubit register allows the list to be permuted in quantum superposition.

Thus we obtain on the qubit q0 the quantum state | 1> if the permuted list is sorted in a decreasing way otherwise the quantum state | 0>.

The OpenQASM code of the quantum algorithm for performing permutations is as follows:

gate permuter a, b, c, d, f, g, i, j, k, l, m, n, o, p {
  cswap k, a, c;
  cswap l, a, f;
  cswap m, a, i;
  cswap k, b, d;
  cswap l, b, g;
  cswap m, b, j;
  cswap n, c, f;
  cswap o, c, i;
  cswap n, d, g;
  cswap o, d, j;
  cswap p, f, i;
  cswap p, g, j;
}
Amplification of the result

I’m going to call this part of my algorithm amplification: the idea is to put the qubit a, b, m, n at | 00>, | 00>, | 00>, | 00> if the list is unsorted. If the list is sorted then the quantum state of a, b, m, n should not be changed.

So we should measure the following result: | 00>, | 00>, | 00>, | 00> when the list is unsorted and a, b, m, n with the input digits in sorted order (in the case in our example this means that there is a probability of measuring the state | 11>, | 10>, | 01>, | 00> either 3,2,1,0 or the sorted list).

The circuit of the quantum amplifier is as follows:

The circuit is based on a series of quantum gate AND applied to the output state q0 AND the number of the list. When the qubit q0 indicates that the list is sorted it is at | 1> and leaves the state of the qubits a, b, m, n at their input state (or permuted by superposition). When the qubit q0 indicates that the list is unsorted it is in the state | 0> the application of the AND gate will thus set the qubits a, b, m, n to | 0>.

The amplifier code is as follows according to a quantum algorithm encoded in OpenQASM:

gate amplifier2 a, b, c, d, f, g, i, j, k, l, m, n, o, p, q, r, v {
  ccx a, k, l;
  swap a, l;
  ccx b, k, m;
  swap b, m;
  ccx c, k, n;
  swap c, n;
  ccx d, k, o;
  swap d, o;
  ccx f, k, p;
  swap f, p;
  ccx g, k, q;
  swap g, q;
  ccx i, k, r;
  swap i, r;
  ccx j, k, v;
  swap j, v;
}
Complete quantum algorithm for descending sorting of a list of four digits:

Here is the circuit used to sort the following list: a = 0, b = 2, m = 3, n = 1.

It is easily possible to initialize the circuit with another list by modifying the initialization of registers a, b, m, n. Also the current algorithm allows to sort numbers coded on 2 qubits it remains possible to modify the algorithm according to the same principle to sort numbers stored on 3 qubits and consider a list of more than 4 elements (it is then necessary to multiply the number of qubit registers to store the entry list).

The complete code is as follows in openQASM:

OPENQASM 2.0;
include "qelib1.inc";
gate andG1 a, b, c {
  ccx a, b, c;
  swap b, c;
}

gate andG2 a, b, c {
  ccx a, b, c;
  swap b, c;
}

gate andG3 a, b, c {
  ccx a, b, c;
  swap b, c;
}

gate orG1 a, b, c {
  x a;
  x b;
  ccx a, b, c;
  x a;
  x b;
  swap b, c;
}

gate andG4 a, b, c {
  ccx a, b, c;
  swap b, c;
}

gate orG2 a, b, c {
  x a;
  x b;
  ccx a, b, c;
  x a;
  x b;
  swap b, c;
}

gate comparator a, b, c, d, f, g, i, j, k, l {
  x d;
  x j;
  x l;
  andG1 b, d, f;
  andG2 a, b, g;
  andG3 a, f, i;
  orG1 b, f, j;
  x c;
  andG4 c, f, k;
  orG2 d, f, l;
}

gate comparator2 a, b, c, d, f, g, i, j, k, l {
  x d;
  x j;
  x l;
  andG1 b, d, f;
  andG2 a, b, g;
  andG3 a, f, i;
  orG1 b, f, j;
  x c;
  andG4 c, f, k;
  orG2 d, f, l;
  x d;
  swap b, g;
}

gate comparator3 a, b, c, d, f, g, i, j, k, l {
  x d;
  x j;
  x l;
  andG1 b, d, f;
  andG2 a, b, g;
  andG3 a, f, i;
  orG1 b, f, j;
  x c;
  andG4 c, f, k;
  orG2 d, f, l;
  swap d, i;
  x d;
  swap b, g;
}

gate comparator4 a, b, c, d, f, g, i, j, k, l {
  x d;
  x j;
  x l;
  andG1 b, d, f;
  andG2 a, b, g;
  andG3 a, f, i;
  orG1 b, f, j;
  x c;
  andG4 c, f, k;
  x c;
  orG2 d, f, l;
  swap d, i;
  x d;
  swap b, g;
}

gate permutation a, b, c, d, f, g, i, j, k, l, m, n, o, p {
  ccx a, c, k;
  ccx a, f, l;
  ccx a, i, m;
  ccx b, d, k;
  ccx b, g, l;
  ccx b, j, m;
  ccx c, f, n;
  ccx c, i, o;
  ccx d, g, n;
  ccx d, j, o;
  ccx f, i, p;
  ccx g, j, p;
}

gate andOnCompare a, b, c, d, f {
  ccx a, b, d;
  swap b, d;
  ccx b, c, f;
  swap c, f;
}

gate permuter a, b, c, d, f, g, i, j, k, l, m, n, o, p {
  cswap k, a, c;
  cswap l, a, f;
  cswap m, a, i;
  cswap k, b, d;
  cswap l, b, g;
  cswap m, b, j;
  cswap n, c, f;
  cswap o, c, i;
  cswap n, d, g;
  cswap o, d, j;
  cswap p, f, i;
  cswap p, g, j;
}

gate amplifier a, b, c, d, f, g, i, j, k, l, m, n, o, p, q, r, v {
  ccx l, a, m;
  swap a, m;
  ccx l, b, n;
  swap b, n;
  ccx l, c, o;
  swap c, o;
  ccx l, d, p;
  swap d, p;
  ccx l, f, q;
  swap f, q;
  ccx l, f, q;
  swap f, q;
  ccx l, g, r;
  swap g, r;
  ccx l, i, v;
  swap i, v;
  ccx l, j, k;
  swap j, k;
}

gate amplifier1 a, b, c, d, f, g, i, j, k, l, m, n, o, p, q, r, v {
  ccx a, l, m;
  swap a, m;
  ccx b, l, n;
  swap b, n;
  ccx c, l, o;
  swap c, o;
  ccx d, l, p;
  swap d, p;
  ccx f, l, q;
  swap f, q;
  ccx f, l, q;
  swap f, q;
  ccx g, l, r;
  swap g, r;
  ccx i, l, v;
  swap i, v;
  ccx j, k, l;
  swap j, k;
}

gate amplifier2 a, b, c, d, f, g, i, j, k, l, m, n, o, p, q, r, v {
  ccx a, k, l;
  swap a, l;
  ccx b, k, m;
  swap b, m;
  ccx c, k, n;
  swap c, n;
  ccx d, k, o;
  swap d, o;
  ccx f, k, p;
  swap f, p;
  ccx g, k, q;
  swap g, q;
  ccx i, k, r;
  swap i, r;
  ccx j, k, v;
  swap j, v;
}

qreg a[2];
qreg b[2];
qreg m[2];
qreg n[2];
qreg c[1];
qreg o[1];
qreg q[1];
qreg d[1];
qreg g[1];
qreg j[1];
qreg k[1];
qreg l[1];
qreg r[1];
qreg uu[1];
qreg zz[1];
qreg control[6];
creg sorted[8];

reset a[0];
reset a[1];
reset b[0];
reset b[1];
reset m[0];
reset m[1];
reset n[0];
reset n[1];
reset c[0];
reset o[0];
reset q[0];
reset d[0];
reset g[0];
reset j[0];
reset k[0];
reset l[0];
reset r[0];
reset uu[0];
h control[0];
h control[1];
h control[2];
h control[3];
h control[4];
h control[5];
reset a[0];
reset a[1];
reset b[0];
x b[1];
x m[0];
x m[1];
reset n[1];
reset c[0];
reset d[0];
reset g[0];
reset j[0];
reset k[0];
reset l[0];
x n[0];
permuter a[0],a[1],b[0],b[1],m[0],m[1],n[0],n[1],control[0],control[1],control[2],control[3],control[4],control[5];
comparator4 a[0],a[1],b[0],b[1],c[0],d[0],g[0],j[0],k[0],l[0];
reset zz[0];
reset d[0];
reset g[0];
reset j[0];
reset k[0];
reset l[0];
comparator4 b[0],b[1],m[0],m[1],o[0],d[0],g[0],j[0],k[0],l[0];
reset d[0];
reset g[0];
reset j[0];
reset k[0];
reset l[0];
comparator4 m[0],m[1],n[0],n[1],q[0],d[0],g[0],j[0],k[0],l[0];
andOnCompare c[0],o[0],q[0],r[0],uu[0];
reset d[0];
reset g[0];
reset j[0];
reset k[0];
reset l[0];
reset r[0];
reset uu[0];
amplifier2 a[0],a[1],b[0],b[1],m[0],m[1],n[0],n[1],q[0],d[0],g[0],j[0],k[0],l[0],r[0],uu[0],zz[0];
measure a[0] -> sorted[0];
measure a[1] -> sorted[1];
measure b[0] -> sorted[2];
measure b[1] -> sorted[3];
measure m[0] -> sorted[4];
measure m[1] -> sorted[5];
measure n[0] -> sorted[6];
measure n[1] -> sorted[7];

Here is the Python Qiskit code for my quantum sorting algorithm:

from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit
from numpy import pi

qreg_a = QuantumRegister(2, 'a')
qreg_b = QuantumRegister(2, 'b')
qreg_m = QuantumRegister(2, 'm')
qreg_n = QuantumRegister(2, 'n')
qreg_c = QuantumRegister(1, 'c')
qreg_o = QuantumRegister(1, 'o')
qreg_q = QuantumRegister(1, 'q')
qreg_d = QuantumRegister(1, 'd')
qreg_g = QuantumRegister(1, 'g')
qreg_j = QuantumRegister(1, 'j')
qreg_k = QuantumRegister(1, 'k')
qreg_l = QuantumRegister(1, 'l')
qreg_r = QuantumRegister(1, 'r')
qreg_uu = QuantumRegister(1, 'uu')
qreg_zz = QuantumRegister(1, 'zz')
qreg_control = QuantumRegister(6, 'control')
creg_sorted = ClassicalRegister(8, 'sorted')
circuit = QuantumCircuit(qreg_a, qreg_b, qreg_m, qreg_n, qreg_c, qreg_o, qreg_q, qreg_d, qreg_g, qreg_j, qreg_k, qreg_l, qreg_r, qreg_uu, qreg_zz, qreg_control, creg_sorted)

circuit.x(qreg_b[1])
circuit.x(qreg_m[0])
circuit.x(qreg_m[1])
circuit.x(qreg_n[0])
circuit.x(qreg_j[0])
circuit.x(qreg_l[0])
circuit.h(qreg_control[0])
circuit.cswap(qreg_control[0], qreg_a[0], qreg_b[0])
circuit.cswap(qreg_control[0], qreg_a[1], qreg_b[1])
circuit.h(qreg_control[1])
circuit.cswap(qreg_control[1], qreg_a[0], qreg_m[0])
circuit.cswap(qreg_control[1], qreg_a[1], qreg_m[1])
circuit.h(qreg_control[2])
circuit.cswap(qreg_control[2], qreg_a[0], qreg_n[0])
circuit.cswap(qreg_control[2], qreg_a[1], qreg_n[1])
circuit.h(qreg_control[3])
circuit.cswap(qreg_control[3], qreg_b[0], qreg_m[0])
circuit.cswap(qreg_control[3], qreg_b[1], qreg_m[1])
circuit.h(qreg_control[4])
circuit.cswap(qreg_control[4], qreg_b[0], qreg_n[0])
circuit.x(qreg_b[0])
circuit.cswap(qreg_control[4], qreg_b[1], qreg_n[1])
circuit.x(qreg_b[1])
circuit.ccx(qreg_a[1], qreg_b[1], qreg_c[0])
circuit.ccx(qreg_a[0], qreg_a[1], qreg_d[0])
circuit.swap(qreg_a[1], qreg_d[0])
circuit.x(qreg_a[1])
circuit.swap(qreg_b[1], qreg_c[0])
circuit.ccx(qreg_a[0], qreg_c[0], qreg_g[0])
circuit.swap(qreg_c[0], qreg_g[0])
circuit.x(qreg_c[0])
circuit.ccx(qreg_a[1], qreg_c[0], qreg_j[0])
circuit.x(qreg_c[0])
circuit.swap(qreg_c[0], qreg_j[0])
circuit.reset(qreg_j[0])
circuit.x(qreg_j[0])
circuit.x(qreg_a[1])
circuit.swap(qreg_a[1], qreg_d[0])
circuit.reset(qreg_d[0])
circuit.ccx(qreg_b[0], qreg_c[0], qreg_k[0])
circuit.swap(qreg_c[0], qreg_k[0])
circuit.x(qreg_c[0])
circuit.reset(qreg_k[0])
circuit.x(qreg_b[0])
circuit.x(qreg_b[1])
circuit.ccx(qreg_b[1], qreg_c[0], qreg_l[0])
circuit.x(qreg_c[0])
circuit.swap(qreg_c[0], qreg_l[0])
circuit.reset(qreg_l[0])
circuit.x(qreg_l[0])
circuit.x(qreg_b[1])
circuit.swap(qreg_b[1], qreg_g[0])
circuit.reset(qreg_g[0])
circuit.x(qreg_b[1])
circuit.h(qreg_control[5])
circuit.cswap(qreg_control[5], qreg_m[0], qreg_n[0])
circuit.x(qreg_m[0])
circuit.x(qreg_n[0])
circuit.cswap(qreg_control[5], qreg_m[1], qreg_n[1])
circuit.x(qreg_m[1])
circuit.ccx(qreg_b[1], qreg_m[1], qreg_o[0])
circuit.ccx(qreg_b[0], qreg_b[1], qreg_d[0])
circuit.swap(qreg_b[1], qreg_d[0])
circuit.x(qreg_b[1])
circuit.swap(qreg_m[1], qreg_o[0])
circuit.ccx(qreg_b[0], qreg_o[0], qreg_g[0])
circuit.swap(qreg_o[0], qreg_g[0])
circuit.x(qreg_o[0])
circuit.ccx(qreg_b[1], qreg_o[0], qreg_j[0])
circuit.x(qreg_o[0])
circuit.swap(qreg_o[0], qreg_j[0])
circuit.reset(qreg_j[0])
circuit.x(qreg_j[0])
circuit.x(qreg_b[1])
circuit.swap(qreg_b[1], qreg_d[0])
circuit.reset(qreg_d[0])
circuit.ccx(qreg_m[0], qreg_o[0], qreg_k[0])
circuit.swap(qreg_o[0], qreg_k[0])
circuit.reset(qreg_k[0])
circuit.x(qreg_o[0])
circuit.x(qreg_m[0])
circuit.x(qreg_m[1])
circuit.ccx(qreg_m[1], qreg_o[0], qreg_l[0])
circuit.x(qreg_o[0])
circuit.swap(qreg_o[0], qreg_l[0])
circuit.ccx(qreg_c[0], qreg_o[0], qreg_r[0])
circuit.reset(qreg_l[0])
circuit.x(qreg_l[0])
circuit.swap(qreg_o[0], qreg_r[0])
circuit.reset(qreg_r[0])
circuit.x(qreg_m[1])
circuit.swap(qreg_m[1], qreg_g[0])
circuit.reset(qreg_g[0])
circuit.x(qreg_m[1])
circuit.x(qreg_n[1])
circuit.ccx(qreg_m[1], qreg_n[1], qreg_q[0])
circuit.ccx(qreg_m[0], qreg_m[1], qreg_d[0])
circuit.swap(qreg_m[1], qreg_d[0])
circuit.x(qreg_m[1])
circuit.swap(qreg_n[1], qreg_q[0])
circuit.ccx(qreg_m[0], qreg_q[0], qreg_g[0])
circuit.swap(qreg_q[0], qreg_g[0])
circuit.x(qreg_q[0])
circuit.ccx(qreg_m[1], qreg_q[0], qreg_j[0])
circuit.x(qreg_q[0])
circuit.swap(qreg_q[0], qreg_j[0])
circuit.reset(qreg_j[0])
circuit.x(qreg_m[1])
circuit.swap(qreg_m[1], qreg_d[0])
circuit.reset(qreg_d[0])
circuit.ccx(qreg_n[0], qreg_q[0], qreg_k[0])
circuit.swap(qreg_q[0], qreg_k[0])
circuit.reset(qreg_k[0])
circuit.x(qreg_q[0])
circuit.x(qreg_n[0])
circuit.x(qreg_n[1])
circuit.ccx(qreg_n[1], qreg_q[0], qreg_l[0])
circuit.x(qreg_q[0])
circuit.swap(qreg_q[0], qreg_l[0])
circuit.reset(qreg_l[0])
circuit.ccx(qreg_o[0], qreg_q[0], qreg_uu[0])
circuit.swap(qreg_q[0], qreg_uu[0])
circuit.reset(qreg_uu[0])
circuit.ccx(qreg_a[0], qreg_q[0], qreg_d[0])
circuit.swap(qreg_a[0], qreg_d[0])
circuit.x(qreg_n[1])
circuit.swap(qreg_n[1], qreg_g[0])
circuit.reset(qreg_g[0])
circuit.ccx(qreg_a[1], qreg_q[0], qreg_g[0])
circuit.swap(qreg_a[1], qreg_g[0])
circuit.ccx(qreg_b[0], qreg_q[0], qreg_j[0])
circuit.swap(qreg_b[0], qreg_j[0])
circuit.ccx(qreg_b[1], qreg_q[0], qreg_k[0])
circuit.swap(qreg_b[1], qreg_k[0])
circuit.ccx(qreg_m[0], qreg_q[0], qreg_l[0])
circuit.swap(qreg_m[0], qreg_l[0])
circuit.ccx(qreg_m[1], qreg_q[0], qreg_r[0])
circuit.swap(qreg_m[1], qreg_r[0])
circuit.ccx(qreg_n[0], qreg_q[0], qreg_uu[0])
circuit.swap(qreg_n[0], qreg_uu[0])
circuit.x(qreg_n[1])
circuit.ccx(qreg_n[1], qreg_q[0], qreg_zz[0])
circuit.swap(qreg_n[1], qreg_zz[0])
circuit.measure(qreg_a[0], creg_sorted[0])
circuit.measure(qreg_a[1], creg_sorted[1])
circuit.measure(qreg_b[0], creg_sorted[2])
circuit.measure(qreg_b[1], creg_sorted[3])
circuit.measure(qreg_m[0], creg_sorted[4])
circuit.measure(qreg_m[1], creg_sorted[5])
circuit.measure(qreg_n[0], creg_sorted[6])
circuit.measure(qreg_n[1], creg_sorted[7])

Quantum sorting algorithm circuit test with IBM qiskit (python)

The tests are carried out by starting the algorithm on the quantum simulator:

To start the quantum algorithm, you must first initialize:

%matplotlib inline
# Importing standard Qiskit libraries
from qiskit import QuantumCircuit, execute, Aer, IBMQ
from qiskit.compiler import transpile, assemble
from qiskit.tools.jupyter import *
from qiskit.visualization import *
from iqx import *

# Loading your IBM Q account(s)
provider = IBMQ.load_account()

And to perform the test for example by executing the quantum circuit 100 times and displaying the probability of measurement in the form of a histogram:

backend = Aer.get_backend('qasm_simulator')
results = execute(circuit, backend=backend, shots=100).result()
answer = results.get_counts()
plot_histogram(answer)

We obtain the result which confirms that with Quantum sort algorithm we have more change in measuring the quantum state of the sorted list than the other combinations (in my test 5%):

After 200 shots i get :

Quantum Sort & Internal links :

http://128mots.com/index.php/en/category/non-classe-en/