Quantum computing in Rust, part 1

#programming #rust 2019-10-28

This essay should serve as an introduction to both quantum computing as well as the trait system of Rust.

This project started on a Sunday night when I should've gone to bed, but wanted to procrastinate and do something.

I was watching Growing a Language by Guy Steele, enjoying the incremental step-by-step approach he had in his talk, describing the construction of a programming language. I figured it would be fun to use a similar approach to build and teach something else from the fundamentals up.

About half a year ago, I had been reading a bit of Quantum Computing for the very curious. I had read the content with a lot of curiosity and interest indeed, and kept up with the spaced repetition question cards for a short while.

I've been pretty much in love with Rust, as far as programming languages go. The tooling with amazing errors and hints, the type, trait and borrow systems that always have your back, the super kind and wholesome community, the blazing speed and ease of concurrency, guaranteed safety, all that jazz. ❤️🦀

I decided it could be a fun experience to combine these three. I created a new repository, started writing a quantum computer simulator in Rust, with a focus on building from primitives upwards. In about four hours, I had this first part done, including writing this essay & fixing bugs. Happy reading!

Prequisites

Let's start with some basic terminology.

Number: The simplest unit. A single value denoting a single point on a continuous line of one-dimensional values. Examples: 0, 0.3.
Imaginary number: a conceptual number often denoted with i or j, with the unit value defined as sqrt(-1). Imaginary numbers can be varying scalar multiples of the unit value. Examples: 2i, 0.3i.
Vector: a single value, whose definition consists of multiple singular values. A two-dimensional vector consists of two one-dimensional values. If we assume the dimensions are perpendicular, a two-dimensional vector can denote a single point on a two-dimensional plane. Examples: [2, 3], [0.2, 0.9].
Complex number: a two-dimensional vector, in which one singular value is a real number and the other is an imaginary number. Examples: [2, 3i], [1, 0i]. Often represented as a sum, optionally simplified, e.g. 2 + 3i, 1.
Rust: A programming language. This essay assumes minimal basic understanding: you have installed rustup and cargo, hopefully some editor plugin(s) to give you tooltips and error messages, and you know how to cargo run your program. You have used a crate (the rust name for a library) as a dependency, or you'll quickly see how in the first steps.

Setup

Next up, let's create our project:

# kvantti is quantum in Finnish
cargo new --lib kvantti
     Created library `kvantti` package

We need two dependencies. Edit your Cargo.toml file:

[dependencies]
num-complex = "0.2"
float-cmp = "0.5.3"

Today's focus is implementing a Ket. Add use statements in your lib.rs:

pub mod ket;
use crate::ket::*;

Create the file src/ket.rs. Add use statements of the num-complex crate and approx_eq macro in it:

use float_cmp::approx_eq;
use num_complex::Complex64;

The rest of this essay will focus on this file.

Struct and constants

A ket is today's fundamental type. It is a struct with two components. These components, individually, are complex numbers.

#[derive(Debug, Copy, Clone)]
pub struct Ket {
  first: Complex64,
  second: Complex64,
}

Let's define a couple of helper constants in the right type. These correspond to the real values 0 and 1, but are actually complex numbers with a real and imaginary parts, and of the correct type Complex64.

pub const COMPLEX_ZERO: Complex64 =
  Complex64 { re: 0.0, im: 0.0 };
pub const COMPLEX_ONE: Complex64 =
  Complex64 { re: 1.0, im: 0.0 };

Additionally, let's define a couple of very primitive kets. A ket with the value [1, 0] is analogous to the classical bit 0. It is also represented by the symbol |0>.

pub const KET_ZERO: Ket = Ket {
  first: COMPLEX_ONE,
  second: COMPLEX_ZERO,
};

Similarly, a ket with the value [0, 1]. This is analogous to the classical bit 1, and has the symbol |1>.

pub const KET_ONE: Ket = Ket {
  first: COMPLEX_ZERO,
  second: COMPLEX_ONE,
};

Equality

It would be useful to know whether two kets are equal to each other. This is possible with Rust's impl keyword and the trait system: we need to implement the PartialEq and Eq traits:

impl PartialEq for Ket {
  fn eq(&self, other: &Self) -> bool {
    self.first == other.first
    && self.second == other.second
  }
}
impl Eq for Ket {}

One of the magic bits here is that Complex64 also implements PartialEq for itself, which means we can just use the == operator in the implementation here for .first and .second value comparisons, and it will just work.

That's it! Now Rust knows how to compare two kets with the same operators. Let's test this out:

#[test]
fn ket_zero_equal_to_itself() {
  assert!(KET_ZERO == KET_ZERO)
}

#[test]
fn ket_one_equal_to_itself() {
  assert!(KET_ONE == KET_ONE)
}

#[test]
fn ket_zero_not_equal_to_ket_one() {
  assert!(KET_ZERO != KET_ONE)
}

Addition

Let's implement some more features for kets. Addition is pretty useful:

use std::ops::Add;
impl Add for Ket {
  type Output = Self;

  fn add(self, other: Self) -> Self {
    Self {
      first: self.first + other.first,
      second: self.second + other.second,
    }
  }
}

#[test]
fn ket_zero_add_ket_one() {
  let sum = KET_ZERO + KET_ONE;
  assert!(
    sum
      == Ket {
        first: COMPLEX_ONE,
        second: COMPLEX_ONE,
      },
  )
}

Here as well, our Add implementation is just using the already-implemented addition operator for the Complex64 numbers. How cool is that?

Multiplication

Let's implement scalar multiplication for kets; multiplying a Ket with a single Complex64 number.

use std::ops::Mul;
impl Mul<Complex64> for Ket {
  type Output = Ket;

  fn mul(self, rhs: Complex64) -> Ket {
    Ket {
      first: self.first * rhs,
      second: self.second * rhs,
    }
  }
}

#[test]
fn mul_ket_zero_with_one() {
  assert!(KET_ZERO == KET_ZERO * COMPLEX_ONE);
}

#[test]
fn mul_ket_one_with_one() {
  assert!(KET_ONE == KET_ONE * COMPLEX_ONE);
}

Here we needed to be a bit more careful: the multiplication has different types on its left and right hand sides. This implemented Ket multiplying a Complex64, returning a Ket.

We also want to have the multiplication work the other way around - especially considering the common written notation of 0.3|0>, a complex scalar as an amplitude for the KET_ZERO.

impl Mul<Ket> for Complex64 {
  type Output = Ket;

  fn mul(self, rhs: Ket) -> Ket {
    Ket {
      first: self * rhs.first,
      second: self * rhs.second,
    }
  }
}

#[test]
fn mul_one_with_ket_zero() {
  assert!(KET_ZERO * COMPLEX_ONE == KET_ZERO);
}

#[test]
fn mul_one_with_ket_one() {
  assert!(KET_ONE * COMPLEX_ONE == KET_ONE);
}

What is especially noteworthy here is that we extended a type coming from a library we did not create.

Arithmetic

At this point, we can do pretty extensive arithmetic with kets and complex numbers, all while carefully typechecked by the compiler:

#[test]
fn ket_arithmetic() {
  let a = Complex64::from(0.6) * KET_ZERO;
  let b = Complex64::from(0.8) * KET_ONE;
  let c = a + b;

  assert!(
    c == Ket {
      first: Complex64::from(0.6),
      second: Complex64::from(0.8),
    }
  )
}

Validation

Quantum states actually have additional validity constraints. We can define our custom trait for valid quantum states, that requires a validation function to be present for the structs that claim to have that trait.

pub trait ValidQuantumState {
  fn is_valid(&self) -> bool;
}

Then we can make sure ket has that trait by implementing is_valid on it:

// The sums of the squares of the amplitudes must be equal to 1
// Amplitude of a complex number x is |x|, available as .norm()
// in the Complex64 type
impl ValidQuantumState for Ket {
  fn is_valid(&self) -> bool {
    let a = self.first.norm();
    let b = self.second.norm();
    let result = (a * a) + (b * b);
    approx_eq!(f64, result, 1.0, ulps = 2)
  }
}

One special thing here is that now ket structs have a new method: every single ket object in our code can be asked if it .is_valid():

#[test]
fn ket_zero_valid() {
  assert_eq!(KET_ZERO.is_valid(), true);
}

#[test]
fn ket_one_valid() {
  assert_eq!(KET_ONE.is_valid(), true);
}

#[test]
fn ket_invalid() {
  assert_eq!((KET_ONE + KET_ZERO).is_valid(), false);
}

We can now perform basic operations on kets, fundamental units of quantum computing, and verify that we have ended up with a valid quantum state at the end:

#[test]
fn ket_arithmetic_valid() {
  let a = Complex64 { re: 0.5, im: 0.5 };
  let b = Complex64 {
    re: 0.0_f64,
    im: 1.0 / 2.0_f64.sqrt(),
  };
  let a = a * KET_ZERO;
  let b = b * KET_ONE;
  let c = a + b;
  assert_eq!(c.is_valid(), true)
}

Note that, in this example, we used kets with both real and imaginary parts in their components. Our implementation took care of all the necessary steps for performing the arithmetic operations correctly.

Additionally, because we declared ValidQuantumState as a trait, any future struct for alternative notations could also be constrained with same validation requirements.

Outro

That's it! We've now implemented Ket, a struct for representing a value in quantum computing. We've implemented basic arithmetic operations, Add between two kets and Mul between a ket and a complex number. We've created the trait ValidQuantumState and made Ket implement it by creating an is_valid() function for it. We have comprehensive tests for it.

a screenshot of passed tests for the program described in this essay

Thank you for reading!

link to the repository

upcoming next parts will be linked here later