Introduction

This book only contains the quick start guide from quantr's repository and a note on memory performance. In the future, it will serve as extended documentation to quantr, in addition to explaining the theory and logic behind the crate.

Quick Start Guide

This guide walks through an implementation of Grover's algorithm using quantr 0.6.0. It's aimed at beginners in Rust and requires a little knowledge of the console. Moreover, it's assumed that Rust and Cargo are installed.

A good starting point to learn Rust is The Rust Book. Likewise, Qiskit offers a good explanation of Grover's. This guide does not attempt to explain either of these subjects in detail.

The complete code that is built from following this guide is available at the end. Or, the code can be found in examples/grovers.rs, and ran from the root directory with cargo run --example grovers.

Open the console, and create a new Rust project (known as a cargo package) by running

cargo new grovers_example

This will create a new directory called grovers_example containing the necessary files for a Rust project. Enter this directory.

Add the latest version of quantr as a dependency by running cargo add quantr on the console. This should add quantr below [dependecies] in you Cargo.toml file. Then, run cargo build. This will download the quantr crate from crates.io and make it accessible for your project.

Once quantr has been installed, open src/main.rs. This is where the subsequent code will be written to implement Grover's algorithm.

Add the following lines to the top of main.rs, and before fn main():

use quantr::{Circuit, Gate, Measurement, Printer};

These lines import the structs and enums that will be used throughout this guide.

Rust begins execution of the program by calling the main() function. So, the rest of the code will be inserted into this function. Let's first initialise a three qubit circuit:

let mut circuit: Circuit = Circuit::new(3).unwrap();

Grover's algorithm requires that the starting state is in a superposition of all basis states with equal amplitudes. This can be achieved by adding a Hadamard gate to each wire, that is to wires 0, 1 and 2:

circuit.add_repeating_gate(Gate::H, &[0, 1, 2]).unwrap();

The .unwrap() forces the program to quit if there is an error in adding these gates, such as adding a gate to a non-existent wire. There are no errors in this example, so the method .unwrap() does nothing.

Let's visualise the circuit that has been built so far (or at any other time throughout this guide) by adding the following:

let mut printer: Printer = Printer::new(&circuit);
printer.print_diagram();

This will print a circuit diagram to the console. This can be seen by running the program by entering cargo run while in the directory that cargo built.

The next step in the algorithm requires the oracle to be defined. This is a function built from unitary gates that flips the sign of the state that corresponds to a 'solution' of the searching function. In this example, the states |110> and |111> are chosen to be the solution states.

This is implemented by adding a controlled-z gate targeting the 0th wire, with its control node placed on the 1st wire; the first and second wire from top to bottom in a circuit diagram respectively:

circuit.add_gate(Gate::CZ(1), 0).unwrap();

The second argument of circuit.add_gate specifies which wire is the target, and the field of the variant Gate::CZ specifies the control wire.

With the solution states marked, these amplitudes are amplified so that solution states are more likely to be measured than other non-solution states. This can be achieved by adding:

circuit.add_repeating_gate(Gate::H, &[0, 1, 2]).unwrap()
    .add_repeating_gate(Gate::X, &[0, 1, 2]).unwrap();

// CC-Z gate
circuit.add_gate(Gate::H, 2).unwrap()
    .add_gate(Gate::Toffoli(0, 1), 2).unwrap()
    .add_gate(Gate::H, 2).unwrap();

circuit.add_repeating_gate(Gate::X, &[0, 1, 2]).unwrap()
    .add_repeating_gate(Gate::H, &[0, 1, 2]).unwrap();

This completes the construction of Grover's algorithm. To make sure that the gates are placed correctly, run the printing code as shown before. Once checked that it's correct, the circuit can be simulated by calling

let simulated_circuit: SimulatedCircuit = circuit.simulate();

This effectively attaches the |000> register to the circuit, resulting in a superposition that can be measured. This superposition, and other information about the simulated circuit, is stored in the simulated_circuit struct that was created upon calling the simulation. This SimulatedCircuit struct allows the circuit to be prepared and measured multiple times to collect a bin count of observed states. This bin count can be found and printed with

if let Measurement::Observable(bin_count) = simulated_circuit.measure_all(500) {
        println!("[Observable] Bin count of observed states.");
        for (state, count) in bin_count {
            println!("|{}> observed {} times", state, count);
        }
    } 

The above prints the number of times each state was observed over 500 measurements. In this situation, the amplitude amplification results in a superposition of two states: |110> and |111>.

Note that the above code is explicit in showing that the measurements are physically possible. This is to distinguish from other data that can be taken from circuit, such as the resulting superposition itself. In nature, this cannot be directly observed. However, it can still be useful to view this "theoretical" superposition. The superposition can be viewed explicitly with:

if let Measurement::NonObservable(output_super_position) = simulated_circuit.get_state()
    {
        println!("\n[Non-Observable] The amplitudes of each state in the final superposition.");
        for (state, amplitude) in output_super_position.into_iter() {
            println!("|{}> : {}", state, amplitude);
        }
    }

This completes the construction and measurement of a three qubit Grover's circuit. Other methods in Circuit (which include examples in their documentation) can add gates in other ways. Moreover, custom gates can be built, where examples can be found in examples/qft.rs and examples/custom_gate.rs.

To improve the readability of this code, the numerous unwrap() calls can be removed, requiring the main function declaration to be edited like so:

use ...;
use quantr::QuantrError;

fn main() -> Result<(), QuantrError> {
    ...; 
    Ok(()) 
}

An Ok(()) is returned on the last line; signalling that the program has exited without errors. Then, effectively all unwrap methods called after appending gates can be replaced with a ?. This can be seen explicitly in the example/grovers.rs folder.

The following is the completed code from this tutorial. This can be ran with cargo run --example grovers from the root directory.

use quantr::{Circuit, Gate, Measurement, Printer, QuantrError};

fn main() -> Result<(), QuantrError> {
    let mut circuit = Circuit::new(3)?;

    // Kick state into superposition of equal weights
    circuit.add_repeating_gate(Gate::H, &[0, 1, 2])?;

    // Oracle
    circuit.add_gate(Gate::CZ(1), 0)?;

    // Amplitude amplification
    circuit
        .add_repeating_gate(Gate::H, &[0, 1, 2])?
        .add_repeating_gate(Gate::X, &[0, 1, 2])?
        .add_gate(Gate::H, 2)?
        .add_gate(Gate::Toffoli(0, 1), 2)?
        .add_gate(Gate::H, 2)?
        .add_repeating_gate(Gate::X, &[0, 1, 2])?
        .add_repeating_gate(Gate::H, &[0, 1, 2])?;

    // Prints the circuit in UTF-8
    let mut printer = Printer::new(&circuit);
    printer.print_diagram();

    // Simulates the circuit
    let simulated_circuit = circuit.simulate();
    println!("");

    // Displays bin count of the resulting 500 repeat measurements of
    // superpositions. bin_count is a HashMap<ProductState, usize>.
    if let Measurement::Observable(bin_count) = simulated_circuit.measure_all(500) {
        println!("[Observable] Bin count of observed states.");
        for (state, count) in bin_count {
            println!("|{}> observed {} times", state, count);
        }
    } 

    // Returns the superpsoition that cannot be directly observed.
    if let Measurement::NonObservable(output_super_position) = simulated_circuit.get_state()
    {
        println!("\n[Non-Observable] The amplitudes of each state in the final superposition.");
        for (state, amplitude) in output_super_position.into_iter() {
            println!("|{}> : {}", state, amplitude);
        }
    }

    Ok(())
}

Performance of Quantr 0.4.0

The main optimisation goal for quantr is to minimise the size of the memory allocation required for simulating circuits. Naturally, quantum circuit simulators will have an inherent limitation due to the exponentially increasing size of the complex state vector that grows with the number of qubits. Therefore, this optimisation goal is accomplished by minimising the overhead required to evolve the state vector.

The challenge is made more difficult by developing this library for the use of personal machines, such as laptops and desktops that may only have around 8GB of memory. Assuming that the optimum memory allocation of a n qubit array with f64 complex amplitudes requires 2**(n-6) KiB in Rust, then a primarily calculation states that these target machines can only ever simulate circuits of up to 28 qubits (requires 4GB of memory for the state vector). Moreover, the circuit simulation itself should remain tractable.

With the memory requirements being the main concern, it was chosen to develop quantr without the use of any matrix or linear algebra libraries to represent the unitary gates. Instead, the linear mappings of these gates in the computational basis are explicitly given using functions. Using these maps also allows for easier extrapolation to greater qubit circuits than using (sparse) matrices. For instance, with matrices one may use the tensor product to calculate a single qubit gate acting in a greater tenor space. By only using linear mappings, the states of concern within the tensor space can be extracted and mapped directly. More detail of how quantr works without matrices will be given in a future update of this book.

Memory

As of quantr-0.4.0, the minimisation of the overhead required to simulate a state vector has been mainly accomplished.

This was tested by using the cap crate to find the total memory allocated over the simulation of grover's algorithm with an increasing register size. The results of which are shown in the figure below:

The graph shows that quantr is seemingly successful in achieving its memory optimisation goals: the memory allocated for the simulation converges on the memory required to hold the state vector.

The overhead required to run the circuit can be seen for low qubit simulations. Even though this overhead is near double the size of the state vector, the total memory is less than 1 MiB and is deemed small enough to be of little concern to any personal machine.

The simulation of grovers with more than 18 qubits starts to become intractable. There are a number of optimisations that are still planned to be implemented for future releases of 0.4.x, and hopefully in these releases, tests of up to 28 qubits will become tractable.

More rigorous testing would be required to definitively check that quantr has successfully achieved its memory optimisation goals. One test could include randomising the placement of universal gates within a circuit of fixed qubit size, and then record the average memory consumption of these circuits. Then the register could be increased and the average measurement can be taken again. However, I believe the memory required would not differ too much, and the initial testing above gives a good indication to quantr's performance.

The code that produced the data can be found in the appendix.

Speed

The speed of quantr has been untested, and as of quantr-0.4.0, has not been optimised in this respect. Only after further releases will this crate be tested for speed.

Appendix

Code for obtaining the data in the plot found in the memory section:

use std::alloc;
use cap::Cap;
use quantr::{Circuit, Printer, Gate, QuantrError, states::*};
use std::fs::File;
use std::io::prelude::*;
use std::ops::Div;

#[global_allocator]
static ALLOCATOR: Cap<alloc::System> = Cap::new(alloc::System, usize::max_value());

fn cnot_expand(input_state: ProductState) -> Option<SuperPosition> {
    let register_size = input_state.num_qubits();

    let repeated_one: Vec<Qubit> = vec![Qubit::One; register_size];
    let mut repeated_zero: Vec<Qubit> = repeated_one.clone();
    repeated_zero[register_size-1] = Qubit::Zero;

    if input_state.get_qubits() == repeated_zero {
        Some(SuperPosition::from(ProductState::new(repeated_one.as_slice()).unwrap()))
    } else if input_state.get_qubits() == repeated_one {
        Some(SuperPosition::from(ProductState::new(repeated_zero.as_slice()).unwrap()))
    } else {
        None
    }
}


fn main() -> Result<(), QuantrError>{
    ALLOCATOR.set_limit(usize::max_value()).unwrap();
    let mut file = File::create("quantr-data-plot.txt").unwrap();
    file.write_all("0.4.0\n".as_bytes()).unwrap();

    // Grover's algorithm
    for n in 3..=18 {
        let mut qc: Circuit = Circuit::new(n)?;
    
        let sub_wire_vec: Vec<usize> = Vec::from_iter(0..n-1);

        let all_wire_vec: Vec<usize> = Vec::from_iter(0..n);
        qc.add_repeating_gate(Gate::H, all_wire_vec.as_slice())?
            .add_gate(Gate::CZ(1), 0)?
            .add_repeating_gate(Gate::H, all_wire_vec.as_slice())?
            .add_repeating_gate(Gate::X, all_wire_vec.as_slice())?
            .add_gate(Gate::H, n-1)?
            .add_gate(Gate::Custom(cnot_expand, sub_wire_vec.as_slice(), "X".to_string()), n-1)?
            .add_gate(Gate::H, n-1)?
            .add_repeating_gate(Gate::X, all_wire_vec.as_slice())?
            .add_repeating_gate(Gate::H, all_wire_vec.as_slice())?;

        let mut printer = Printer::new(&qc);
        printer.get_diagram();

        qc.toggle_simulation_progress();

        qc.simulate();

        let memory_used = (ALLOCATOR.allocated() as f32).div(1024f32);
        
        let data_line = format!("{} {}\n", n, memory_used);
        file.write_all(data_line.as_bytes()).unwrap();

        println!("Printed {}", n);
    }

    Ok(())
}