Quantum Types

When developing a quantum algorithm, it can be useful to be able to describe a precise data structure built upon a register of qubits.

Consider for instance an algorithm that requires manipulation of a lot of qubit registers storing (quantum) integers. In that setting, it can become quite painful to manipulate the registers and other ancillae qubits.

Lets consider the following piece of code:

from qat.lang.AQASM import QRoutine, CNOT
from qat.lang.AQASM.arithmetic import add

def compare(bit_length1, bit_length2):
    """ Compares two integers """

    routine = QRoutine()
    reg1 = routine.new_wires(bit_length1)
    reg2 = routine.new_wires(bit_length2)
    overflow = routine.new_wires(1)
    output = routine.new_wires(1)
    routine.set_ancillae(overflow)

    with routine.compute():
        add(bit_length1 + 1, bit_length2).dag()(reg1, overflow, reg2)

    CNOT(overflow, output)
    routine.uncompute()
    
    return routine

rout = compare(3, 3)
rout.display()

This routine compares two integers and stores a boolean value in some output qubit (q6 in the picture).

This is nice, but the code is quite far from its classical (non-reversible) counterpart: pyAQASM comes with two predefined data types that can help us bring this code closer to what we would love to write:

• we had to allocate work memory by hand (overflow)
• we had to tell pyAQASM to compute something (i.e figure out that a comparison can be done using a substraction and an overflow check)
• we had to tell pyAQASM to uncompute what was computed

from qat.lang.AQASM import QInt

def compare(bit_length1, bit_length2):
    """ Compares two integers """

    routine = QRoutine()
    int1 = routine.new_wires(bit_length1, QInt)
    int2 = routine.new_wires(bit_length2, QInt)
    output = routine.new_wires(1)
    (int1 < int2).evaluate(output=output)
    return routine

rout = compare(3, 3)
rout.display()

By simply declaring our registers as QInts, we can compare them using the standard python comparison operator.

So, what is really happenning under the hood?

The expression:

int1 < int2

doesn't do anything per se. It builds an abstract expression waiting to be evaluated.

When calling the evaluate method, a circuit is generated that will recursively evaluate this expression and output a qubit carrying the evaluation result. Here we pass the output qubit as argument to tell the evaluation method to directly store the result in output.

We will now introduce more deeply the two data types that are present in the QLM.

Quantum booleans: QBool

The first data-type and the most simple one is the QBoolArray type. It simply says: "my register is a list of quantum booleans". As such, they can be manipulated using logical operators (and, or, xor, not).

Quantum types are assigned to a register directly at allocation time:

from qat.lang.AQASM import QBoolArray

rout = QRoutine()
qbool = rout.new_wires(2, QBoolArray)

If our qubits are constructed as QBools, we can construct boolean expressions using the standard python operators:

and_clause = qbool[0] & qbool[1]
print(and_clause)

or_clause = qbool[0] | qbool[1]
print(or_clause)

xor_clause = qbool[0] ^ qbool[1]
print(xor_clause)

not_clause = ~ qbool[0]
print(not_clause)

(q[0]&q[1])
(q[0]|q[1])
(q[0]^q[1])
(~ q[0])

There are several ways to make use of these clauses.

1. First, by evaluating the clause and storing the evaluation inside either an ancilla or a pre-allocated output.

rout = QRoutine()
qbool = rout.new_wires(2, QBoolArray)
anc = (qbool[0] & qbool[1]).evaluate()
rout.display()

rout = QRoutine()
qbool = rout.new_wires(2, QBoolArray)
result = rout.new_wires(1)
(qbool[0] & qbool[1]).evaluate(output=result)
rout.display()

2. Second, by directly performing a phase oracle using the formula. This is useful when writing Grover oracles, for instance.

rout = QRoutine()
qbool = rout.new_wires(2, QBoolArray)

(qbool[0] & qbool[1]).phase()
rout.display()

(qbool[0] | qbool[1]).phase()
rout.display()

(qbool[0] ^ qbool[1]).phase()
rout.display()

(~qbool[0]).phase()
rout.display()

3. Finally, one can evaluate the formula inside a context and let pyAQASM perform the uncomputations via a with statement. Notice that this is not necessarily the most efficient way of manipulating formulae. It usually comes with a gate and qubits overhead.

from qat.lang.AQASM import Z

rout = QRoutine()
qbool = rout.new_wires(2, QBoolArray)

with qbool[0] & qbool[1] as condition:
    # Here, condition is a qubit carrying the expected logical value
    Z(condition)

rout.display()

Quantum Integers: QInt

The second quantum type that is provided in qat.lang.AQASM is the QInt class. Registers allocated with this type have overloaded +, -, and * operations that allow to construct arithmetic expressions:

from qat.lang.AQASM import QRoutine, QInt, CNOT

rout = QRoutine()
qint1 = rout.new_wires(10, QInt)
qint2 = rout.new_wires(10, QInt)

print(qint1 + qint2)
print(qint1 - qint2)
print(qint1 * qint2)

(QInt(q[0]..q[9])+QInt(q[10]..q[19]))
(QInt(q[0]..q[9])-QInt(q[10]..q[19]))
(QInt(q[0]..q[9])*QInt(q[10]..q[19]))

These expressions don't trigger any proper quantum circuit generation. The only way to trigger a circuit construction is to affect an expression to a QInt via either +=or -=:

rout = QRoutine()
qint1 = rout.new_wires(4, QInt)
qint2 = rout.new_wires(4, QInt)

qint1 += qint2
rout.display()

qint1 += 5
rout.display()

qint1 -= qint2
rout.display()

qint3 = rout.new_wires(4, QInt)
qint3 += qint1 * qint2 + 6 + qint2
rout.display()

Quantum integers can also be compared:

rout = QRoutine()
qint1 = rout.new_wires(4, QInt)
qint2 = rout.new_wires(4, QInt)

print(qint1 < qint2)
print(qint1 <= qint2)
print(qint1 > qint2)
print(qint1 >= qint2)
print(qint1 == qint2)
print(qint1 != qint2)
print(qint1 == 8)

(QInt(q[0]..q[3]) < QInt(q[4]..q[7]))
(QInt(q[0]..q[3]) <= QInt(q[4]..q[7]))
(QInt(q[0]..q[3]) > QInt(q[4]..q[7]))
(QInt(q[0]..q[3]) >= QInt(q[4]..q[7]))
(QInt(q[0]..q[3]) == QInt(q[4]..q[7]))
(QInt(q[0]..q[3]) != QInt(q[4]..q[7]))
(QInt(q[0]..q[3]) == 8)

These comparisons only produce objects called QClauses that are more or less equivalent to QBools:

rout = QRoutine()
qint1 = rout.new_wires(4, QInt)
qint2 = rout.new_wires(4, QInt)

# One can evaluate them
output = (qint1 < qint2).evaluate()
rout.display()

# Flip a phase depending on their evaluation:
(qint1 < qint2).phase()
rout.display()

# Or use them in a context:
with qint1 < qint2 as condition:
    CNOT(condition, output)

rout.display()

A tiny example: writing a Grover for SAT in a few lines

Thanks to this feature, it becomes really easy to build a Grover's oracle for, say, SAT. Let's assume that we are given a formula in CNF as a list of lists of signed variable indexes (a usual input format for SAT solver).

Our oracle can be generated by the following method:

from functools import reduce

def sat_oracle(nbvars, formula):
    routine = QRoutine()
    qvars = routine.new_wires(nbvars, QBoolArray)

    # And-reduction of all clauses
    reduce(
        lambda a, b: a & b, 
        # Or-reduction of each clause
        (reduce(
            lambda i, j: i | j, 
            (qvars[i - 1] if i >= 1 else ~qvars[- i - 1] for i in clause)
        ) for clause in formula)
    ).phase()

    return routine

formula = [
    (1, 2, -3), (-1, 2, 3), (-1, -4)
]
oracle = sat_oracle(4, formula)
oracle.display()

Quantum Integers: Let's spice things up!

Imagine we need to write some oracle/piece of circuit that has to deal with quantum integers. In this setting, the previously introduced QInt can help reduce the code complexity by a lot.

Consider for instance the oracle for graph coloring introduced in the needle versus haystack notebook.

We can rewrite this oracle in a few lines like so:

def graph_coloring_oracle(graph, bit_length):
    routine = QRoutine()
    colors = [routine.new_wires(bit_length, QInt) for _ in graph.nodes()]
    reduce(
        lambda a, b: a & b,
        (colors[a] != colors[b] for a, b in graph.edges())
    ).phase()
    return routine

import networkx as nx

graph = nx.generators.erdos_renyi_graph(27, 0.5, seed=12334)
oracle = graph_coloring_oracle(graph, 2) # 2 => 4 coloring

# This circuit might be a bit large to display.
print("We use:", oracle.arity, "inputs and", len(oracle.ancillae), "ancillae")

We use: 54 inputs and 190 ancillae

Casting boolean to integers

The previous code uses quite a large number of ancillae (one per edge). One might want to be less greedy and use the counter method also presented in the needle versus haystack notebook.

This can also be done quite efficiently:

def graph_coloring_oracle_counter(graph, bit_length):
    routine = QRoutine()
    colors = [routine.new_wires(bit_length, QInt) for _ in graph.nodes()]
    counter = routine.get_free_ancillae(graph.number_of_edges().bit_length(), QInt)

    with routine.compute():
        for a, b in graph.edges():
            with colors[a] != colors[b] as condition:
                counter += condition.cast_to(QInt)

    (counter == graph.number_of_edges()).phase()
    routine.uncompute()

    return routine

oracle_counter = graph_coloring_oracle_counter(graph, 2) # 2 => 4 coloring
# This circuit might be a bit large to be displayed.
print("We use:", oracle_counter.arity, "inputs and", len(oracle_counter.ancillae), "ancillae")
print("The previous oracle used:", oracle.arity, "inputs and", len(oracle.ancillae), "ancillae")

We use: 54 inputs and 9 ancillae
The previous oracle used: 54 inputs and 190 ancillae