An array of facts on arrays in Q#

by Sarah Kaiser


Post co-authored with Chris Granade, my co-author on Learn Quantum Computing with Python and Q#!

All of the Q#, C# and Python examples in this post can be run online on Binder. It may take a while to build the docker container so read ahead, and you can jump back when it's done. 😊

Normally when you read a post or an article about a quantum programming language like Q#, you'll see stuff about:

  • what qubits are,
  • what a quantum computer even is, or
  • how superposition and entanglement can be used together to solve hard problems.

That's all really important to help understand why quantum computing is so cool, and how you can get started with it, but there is something that's easily lost in all of that: quantum programs are just special kinds of classical programs.

What do we mean by that?
At their core, quantum programs are classical programs that send instructions to quantum devices.
That means that a lot of what you already know about classical programming still applies.
In this post, we'll look at how Q# represents one incredibly common classical data structure in what may seem to be a slightly unusual way, and how that helps make Q# a great classical language for controlling quantum devices.

Arrays in Q#

via GIPHY

Whatever they might be called in a particular language, arrays are an incredibly common and useful data structure for developers.
There can be differences in how they behave from language to language, so it might be helpful to take a look at how they work in Q#.

Consider the following snippet where you are creating two arrays (a and b) in Q#.

mutable a = [2, 4, 6];
let b = a;

// Change the first element of `a` to 1.
set a w/= 0 <- 1;

Message($"{b}");

What will the value of b be after running all the code above?
Reminder you can run all the code in this post on Binder.

via Gfycat

The answer here comes down to the difference between whether we think of a variable as storing a value, or as being a reference to something.
In Q#, everything is a value, so when we define a new variable with let b = a, we tell the Q# compiler that we want the value of b to be equal to whatever the value of a is.

Therefore, the snippet above will print out the array [2, 4, 6], because after we defined b as having the value that a had at that moment ([2, 4, 6]), not a reference to the variable a.
Put differently, b does not know anything about a, let alone any later changes to a.

Thinking of arrays as values also helps explain what w/= is all about in the code above.
In Q#, w/ is a ternary operator (that is, one with three arguments) that makes a new array given: an old array, an index you want to replace, and a new element to put at that index.
For example:

let a = [2, 4, 6] w/ 0 <- 1;
Message($"{a}"); // Prints [1, 4, 6].

Since w/ is an operator, you can use it like +, *, or any other operator to make Q# values:

let a = ([2, 4, 6] w/ 0 <- 1 w/ 2 <- 10) + [20];
Message($"{a}"); // Prints [1, 4, 10, 20].

When updating the value of a mutable variable, Q# provides helpful shorthand for using an operator in-place as an assignment operator:

mutable a = 10;
set a += 1;
Message($"{a}"); // Prints 11.

The same exact shorthand works for w/, so you can use w/= as a shorthand:

mutable a = [2, 4, 6];
// Both of the following lines are equivalent:
set a = a w/ 0 <- 1;
set a w/= 0 <- 1;

What makes all of this work is that in Q#, everything is a value.
The array [2, 4, 6] is a value in precisely the same way as 2 is a value, or that true, "foo", and 3.14 are values.

How do Q# arrays compare to similar concepts in other languages?

In Python, there isn't exactly an array type, so let's look at some related types you might use in a similar way.
Lists, tuples, and strings in Python are ways of organizing collections of elements, so let's compare how they work to Q# arrays.

Tuples and strings are immutable, meaning that they cannot be changed after they are created.
What happens in the following snippet?

a = "Hello world!"
b = a
a = a[:5] + " Cruel" + a[5:]
print(b)

This will print Hello world!, because b is immutable once created.
The third line where we construct a new value for a works because we are not trying to change a's previous value, but give an entirely new one.

C# takes a very similar approach, treating strings as immutable.
Try running the following example in a C# Notebook and see what you get!

var s = "abc";
var t = s;
s = s.Remove(1, 1).Insert(1, "B");
(s, t)

This immutability makes it really easy to reason about side-effects, since nothing else in your Python program can possibly mess with what a is.
Where immutability in Python gets inconvenient, though, is if you want to replace just one element of a tuple or string:

>>> a = "Hello, world!"
>>> a[-1] = "?"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment

To help with this, Python also provides lists, which are really similar to tuples, but are mutable; that is, the contents of lists can be changed after they are created.

>>> a = [2, 4, 6]
>>> a[-1] = 10
>>> a
[2, 4, 10]

One way to think about Q# arrays, then, is as being similar to Python tuples, but with a cool operator (w/) that lets you use them in the same ways as lists even without needing mutable collections.
That lets you get all the benefits and predictability of immutable collections like Python strings and tuples, and like C# strings, but with the flexibility that you would normally expect from mutable collections like Python lists and and C# arrays.

You can use Q# arrays to implement a wide range of classical computing tasks from within your quantum programs, even including things like the quicksort algorithm!

function Sorted<'T>(comparisonFunction : (('T, 'T) -> Bool), inputArray: 'T[]) : 'T[] {
    if (Length(inputArray) <= 1) {
        return inputArray;
    }
    let pivot = Head(inputArray);
    let left = Filtered(comparisonFunction(_, pivot), Rest(inputArray));
    let right = Filtered(Compose(Not, comparisonFunction(_, pivot)), Rest(inputArray));

    return Sorted(comparisonFunction, left) + [pivot] + Sorted(comparisonFunction, right);
}

Because Q# arrays are values, it's really easy to predict how they'll behave in your quantum programs, even as you do things like use the Adjoint functor to run parts of your programs backwards.
Arrays are a great example of how the classical programming features of Q# are designed, making it easy to use for quantum computing 💖

More Resources!

Want to learn more about arrays in Q# or Quantum Computing?
Check out the links below for some good resources! 😀