# wbernoudy/quetzal

Quantum computation simulator. Includes Grover's algorithm and a way to generate the oracle from a classical circuit.
Python Racket TeX Shell
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
Failed to load latest commit information.
circuit-files
Grover.rkt
generate-circuit.sh
oracle-constructor.rkt
quetzal.rkt

# quetzal

A quantum computation simulator written in Racket.

Simulation is achieved by constructing matrices that correspond to the quantum gates. Gates are then applied by multiplying the matrices with the vector that represents the state of the qubits.

## quetzal.rkt: the simulator

This includes the functions required for basic simulation. To use it in your code:

`> (require "quetzal/quetzal.rkt")`

### Usage

First, use `initialize-register`. This function accepts a list of the classical states you want to set the qubits to.

`> (initialize-qubits '(0 1 0)) ; Initialize register with three qubits with the state |010>`

Now, at any point, you can access the n x 1 (for n-qubits) matrix corresponding to the vector representing the state of the qubits stored in the variable `register`.

```> register
(mutable-array #[#[0 0 0 0 0 0 1 0]])```

You can now apply a gate to the register using `apply-gate`, which takes three arguments: a matrix representing the system-state (probably `register`), a list of the qubits which you want to apply the gates to, and the gate itself (in matrix form). `execute` Then sets register to the result of the computation.

```> (apply-gate register '(0 1 2) Toffoli-gate)
(array #[#[0 0 0 0 0 0 0 1]])
> register
(array #[#[0 0 0 0 0 0 0 1]])```

At this point, quetzal provides the gates: `Hadamard-gate`, `Pauli-X-gate`, `Pauli-Y-gate`, `Pauli-Z-gate`, `CNOT-gate`, `QSwap-gate`, and `Toffoli-gate`. You can define your own by doing

```> (define my-gate (matrix [
> 	[a b]
> 	[c d]
> ]))```

The function `measure-register` displays the most likely state for the system to collapse to on measurement and the likelihood of that happening:

```> (measure-register)
The most likely result is |011> with a probability of 0.9991823155432934```

### Extra

I also included a function for printing matrices so they are easier to visualize called `matrix-print`.

```> (matrix-print Toffoli-gate)
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0 ```

## Grover.rkt: an implementation of Grover's algorithm

This includes functions for a basic implementation of Grover's algorithm. Some shortcuts are used to increase efficiency of simulation.

```> (require "quetzal/quetzal.rkt")
> (require "quetzal/Grover.rkt")```

### Usage

The oracle function, in reality a sequence of quantum gates, can be represented by a simple matrix. Thus you can use the `generate-fake-Oracle` function, which takes two arguments: the number of entries in the "database" you are searching (must be a factor of 2), and the item you are searching for. It then outputs a the corresponding matrix.

```> (matrix-print (generate-fake-Oracle 4 2))
1 0 0 0
0 1 0 0
0 0 -1 0
0 0 0 1 ```

The function `Grover` simulates the algorithm. It takes one argument, the matrix representing the oracle function.

```> (Grover (generate-fake-Oracle 64 45))
The number of required qubits is 6
Number of operations required is 7
> (measure-register)
The most likely result is |101101> with a probability of 0.996585680786799```

## oracle-constructor.rkt: simulating a classical circuit for the oracle for Grover's algorithm

### Design

To actually use Grover's algorithm to search a "database", we need a way to convert the search function into the oracle. This is done by first generating a classical circuit which performs the search function, and the simulating this circuit with a quantum circuit. `oracle-constructor.rkt` allows you to input a classical circuit (represented by a boolean expression) and get the quantum circuit which simulates the circuit and acts as the oracle function. You can then input the oracle function (represented by a matrix) into the `Grover` function to perform Grover's algorithm.

### Usage

To use `oracle-constructor.rkt`, do:

```> (require "quetzal/quetzal.rkt")
> (require "quetzal/oracle-constructor.rkt")```

The function `generate-U_ω` generates the oracle. It a boolean expression as its only argument. After it is executed, the matrix representing the oracle operator will be set as `U_ω`, and `input-qubits` will contain the number of input qubits (used later on). For example, for the boolean expression (x0 ∧ x1):

```> (generate-U_ω '(∧ 0 1))
> (matrix-print U_ω)
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
> input-qubits
1```

Besides the `∧` operator, there is also the `∨` and the `¬`. Both `∧` and `∨` take exactly two arguments, while `¬` takes one. You can also use `AND`, `OR` and `NOT` if you'd rather not use Unicode.

Because there are extra qubits required for the simulated circuit (notice that in the above example, 5 qubits are needed despite there only being two inputs), there is a special Grover's algorithm function called `Grover-from-classical-circuit` that takes this into account. To use it, input the `U_ω` and `input-qubits` which are automatically generated after using `generate-U_ω`.

```> (Grover-from-classical-circuit U_ω input-qubits)
The number of required qubits is 5
Number of operations required is 2
> (measure-register)
The most likely result is |11000> with a probability of 0.9999999999999987```

Since the solution to the classical circuit we inputted is |11> we can see that the algorithm was successful.

#### A note on classical circuits

Grover's algorithm expects that there is only one state of the input bits which flips the phase. This means there should only be one solution to the search function, and thus the classical circuit you input. If there is more than one, `generate-U_ω` will not output a valid oracle matrix.

### Generating circuit diagrams using qasm2circ

Every time `generate-U_ω` is called, it creates file at `quetzal/circuit-files/qcircuit.qasm` which corresponds to the quantum circuit created. Using qasm2circ, this file can then be easily converted to PDF format.

I have included a simple bash scipt which handles this. It requires python2 and LaTeX to be installed (python2, latex, and dvipdf must be included in your PATH). After running `generate-U_ω`, do

``````\$ quetzal/generate-circuit.sh
``````

Here's the diagram generated after doing `(generate-U_ω '(∧ (∧ 0 1) (∧ 1 2)))`:

You can’t perform that action at this time.