Arithmetic routines

pyAQASM comes with a pre-implemented set of arithmetic routines. Since there are different approaches to implement arithmetic routines, we provide various implementation of some low-level routines such as additions and additions by a classical constant. Higher level routines are then implemented by calling some implementation of these lower level routines.

The following diagram sums up the various routines and their implementation. Arrows mean “uses”, green boxes indicates the implementation strategy:

  • QFT means QFT-based arithmetic

  • CARRY means ripple-carry based arithmetic

  • INDEP means agnostic. These routines call lower level routines, indepentently from their implementation.

images/arithmetic.png

The routines are separated into three distinct namespaces according to these three types of implementation strategy: QFT, CARRY, INDEP.

Warning

All methods are decorated using @build_gate which turn them into AbstractGates. To access the underlying routine instead of the wrapping gates, the method name can be prefixed with ‘~’.

# will generate a call to an AbstractGate having the QFT as circuit
# implementation
QFT(3)

# will generate a QRoutine object
(~QFT)(3)

The two behaviors are comparable, except that using the U notation allows to skip the inlining step when extracting the circuit (.to_circ method with inline=False) and to link another implementation of gate U later on. Using (~U) will effectively inline the gate no matter what.

QFT-based arithmetic

This package provides some basic arithmetic operations, all implemented using QFT.

Overview

This module provides implementation of a QFT transform and of various arithmetical operations. The adder and the multiplication are inspired of arXiv:1411.5949.

qat.lang.AQASM.qftarith.QFT(reg_size)

Builds a circuit performing a full Quantum Fourier Transform on a given number of qbits.

Let us consider the input state

\[|\psi_{\mathrm{in}}\rangle=\sum_{k=0}^{2^{n}-1}a_{k}|k\rangle\]

with \(|k\rangle=|b_{0}^{(k)},\dots b_{n-1}^{(k)}\rangle\), and the bit ordering defined by the expression \(k= \sum_{p=0}^{n-1}2^{n-1-p}b_{p}^{(k)}\) (most significant bit on the left). The QFT routine transforms this state to the state

\[|\psi_{\mathrm{out}}\rangle\equiv U_{\mathrm{QFT}}|\psi_{\mathrm{in}}\rangle =\sum_{x=0}^{2^{n}-1}\tilde{a}_{x}|x\rangle\]

with the bit ordering defined in a reversed way, i.e \(x=\sum_{q=0}^{n-1}2^{q}b_{q}^{(x)}, |x\rangle= |b_{n-1}^{(x)},\dots,b_{0}^{(x)}\rangle\). The input and output amplitudes are related by the expression:

\[\tilde{a}_{x}=\frac{1}{\sqrt{2^{n}}}\sum_{k=0}^{2^{n}-1} \left(e^{\frac{2i\pi}{2^{n}}}\right)^{xk}a_{k}\]
Parameters

reg_size (int) – the number of qbits to apply the QFT on

Returns

QRoutine

qat.lang.AQASM.qftarith.add(reg_size, reg_size_2)

Builds a circuit performing an addition using two qbits registers. The addition is done ‘in place’. Only the content of the first register is changed:

\[|a\rangle|b\rangle \mapsto |a + b\rangle|b\rangle\]

All additions, unless specified, are modulo \(2^n\) where n is the size of the register holding the result.

Parameters

  • reg_size (int) – the number of qbits on which to perform the addition

  • reg_size_2 (int) – the number of qbits holding the value of the number to add

qat.lang.AQASM.qftarith.add_const(reg_size, constant)

Builds a circuit performing an addition by a constant:

\[|a\rangle \mapsto |a + C\rangle\]

All additions, unless specified, are modulo \(2^n\) where n is the size of the register holding the result.

Parameters

  • reg_size (int) – the number of qbits on which to perform the addition

  • constant (int) – the constant number to add

qat.lang.AQASM.qftarith.mult(reg_size, reg_size_2, res_reg_size)

Builds a circuit performing a multiplication using two qbits registers and storing the result in a third. . Only the content of the third register is changed:

\[|a\rangle|b\rangle|c\rangle \mapsto |a \rangle | b \rangle|c+a\times b\rangle\]

The multiplication is performed by b repeated additions of a into the third register. All additions, unless specified, are modulo \(2^n\) where n is the size of the register holding the result.

Parameters

  • reg_size (int) – the number of qbits of the first register

  • reg_size_2 (int) – the number of qbits holding the value of the number to multiply

  • res_reg_size (int) – the number of qbits holding the final result

qat.lang.AQASM.qftarith.mult_const(reg_size, reg_size_2, constant)

Builds a circuit performing a multiplication by a constant c. Only the content of the second register is changed:

\[|a\rangle|b\rangle \mapsto |a\rangle|b+ a\times c\rangle\]

The multiplication is performed by a repeated additions of c into the second register. All additions, unless specified, are modulo \(2^n\) where n is the size of the register holding the result.

Parameters

  • reg_size (int) – the number of qbits of the first register

  • reg_size_2 (int) – the number of qbits holding the final result (second register)

  • constant (int) – the constant number to multiply

Carry-based arithmetic

Implementation of quantum adders based on arXiv:quant-ph/9511018, arXiv:quant-ph/0410184 and arXiv:0910.2530v1.

qat.lang.AQASM.classarith.cuccaro_add(reg_size, reg_size_2)

Implementation based on arXiv:quant-ph/0410184. Builds a circuit performing an addition using two qbits registers. The addition is done ‘in place’. Only the content of the first register is changed:

\[|a\rangle|b\rangle \mapsto |a + b\rangle|b\rangle\]

All additions, unless specified, are modulo \(2^n\) where n is the size of the register holding the result.

The circuit has size \(6n\) (\(2n\) Toffoli and \(4n\) CNOT).

Parameters

  • reg_size (int) – the number of qbits on which to perform the addition

  • reg_size_2 (int) – the number of qbits holding the value of the number to add

Warning

This routine has public arity reg_size + reg_size_2 but uses 1 additional qubit (it will be automatically allocated at circuit generation time, in the to_circ() method).

qat.lang.AQASM.classarith.add(reg_size, reg_size_2)

Implementation based on arXiv:0910.2530v1. Builds a circuit performing an addition using two qbits registers. The addition is done ‘in place’. Only the content of the first register is changed:

\[|a\rangle|b\rangle \mapsto |a + b\rangle|b\rangle\]

All additions, unless specified, are modulo \(2^n\) where n is the size of the register holding the result.

The circuit has size \(7n\) (\(2n\) Toffoli and \(5n\) CNOT).

Parameters

  • reg_size (int) – the number of qbits on which to perform the addition

  • reg_size_2 (int) – the number of qbits holding the value of the number to add

Note

This adder is the default adder of the namespace qat.lang.AQASM.classarith. This means that linking the full package to the to_circ() method will link this particular adder. If you wish to specifically use another adder ( cuccaro_add() for instance), the adder should linked individually.

qat.lang.AQASM.classarith.add_const(reg_size, constant)

Implementation based on arXiv:quant-ph/9511018. Builds a circuit performing an addition by a constant:

\[|a\rangle \mapsto |a + C\rangle\]
Parameters

  • reg_size (int) – the registers size

  • constant (int) – the constant to add

Warning

This routine has public arity reg_size but uses reg_size - 1 additional qubits (these will be automatically allocated at circuit generation time, in the to_circ() method).

Agnostic/High-level arithmetic

The implementation of these high-level routines is inspired from arXiv:quant-ph/9511018 .

Warning

Most of these AbstractGates/methods require lower level routines that should be linked during the circuit extraction.

reg_size = 10
constant = 8
modulo = 15
gate = add_const_mod(reg_size, constant, modulo)

prog = Program()
qbits = prog.qalloc(gate.arity)
prog.apply(gate, qbits)
circuit = prog.to_circ()

# This circuit will crash at simulation, since it contains high level
# gates with no implementation

circuit_qft = prog.to_circ(link=[qat.lang.AQASM.qftarith])
# This will link an implementation for the abstract gates used in
# our high level gate. This circuit should not crash when simulated.

circuit_class = prog.to_circ(link=[qat.lang.AQASM.classarith])
# Same thing, but using carry-based arithmetic instead of qft-based.
qat.lang.AQASM.arithmetic.modular_exp(reg_size, acc_size, constant, modulus)

Generates a QRoutine performing the following operation:

\[|a\rangle |0 \rangle \mapsto |a\rangle | \textrm{base}^a \mod \textrm{modulus} \rangle\]

acc_size is expected to be of size bitlength(modulus).

This routine is the basis of Shor’s algorithm for number factoring:

from qat.lang.AQASM import *
from qat.lang.AQASM.arithmetic import modular_exp
from qat.lang.AQASM.qftarith import QFT
import qat.lang.AQASM.qftarith as qftarith

modulus = 15
base = 2
bitlength = 4 # We need 4 bits to write 15

shor = Program()
phase_reg = shor.qalloc(2 * bitlength)
acc = shor.qalloc(bitlength)

modular_exp(2 * bitlength, bitlength, base, modulus)(phase_reg, acc)


QFT(2 * bitlength)(phase_reg)

circuit = shor.to_circ(link=[qftarith])

from qat.core.util import statistics

print(statistics(circuit))

{'nbqbits': 19, 'size': 2, 'gates': {'custom gate': 0, 'X': 1, 'H': 3720, 'C-PH': 8988, 'C-C-PH': 1472, 'C-C-CNOT': 128, 'C-C-C-PH': 384, 'C-C-X': 128, 'C-SWAP': 32}, 'measurements': 0, 'resets': 0, 'logic': 0, 'breaks': 0, 'remaps': 0, 'gate_size': 14853}
Parameters

  • reg_control_size – the exponent registers size

  • acc_size – the accumulator size

  • base – the root of the exponentiation

  • modulus – the modulus value

Warning

This routine makes use of Euclide’s algorithms to invert base modulo modulus. In order for this to work, base and modulus need to be coprime.

Warning

This routine has public arity reg_control_size + acc_size but uses acc_size + 1 additional qubits (these will be automatically allocated at circuit generation time, in the to_circ() method).

This number does not include the optional qubits allocated by sub-routines used inside this routine

This routine calls:

qat.lang.AQASM.arithmetic.mult_const_mod(reg_size, acc_size, constant, modulus)

Generates a QRoutine performing the following operation:

\[| a \rangle | b \rangle \mapsto |a \rangle | b + a \times \textrm{constant} \mod \textrm{modulus} \rangle\]
Parameters

  • reg_size (int) – the register size

  • acc_size (int) – the accumulator size

  • constant (int) – the constant to add

  • modulus (int) – the modulus value

Warning

Some additional qubits might be allocated by sub-routines inside this routine.

This routine calls:

qat.lang.AQASM.arithmetic.add_const_mod(reg_size, constant, modulus)

Generates a QRoutine performing the following operation:

\[|a\rangle \mapsto |a + \textrm{constant} \mod \textrm{modulus}\rangle\]
Parameters

  • reg_size (int) – the register’s size

  • constant (int) – the constant to add

  • modulus (int) – the modulus

Warning

This routine has public arity reg_size but uses 2 additional qubits (these will be automatically allocated at circuit generation time, in the to_circ() method).

Some additional qubits might be allocated by sub-routines inside this routine.

This routine calls:

qat.lang.AQASM.arithmetic.mult_const(reg_size, acc_size, constant)

Generates a QRoutine performing a multiplication between a register of size reg_size and a constant, accumulating the result in a register of size acc_size . By default, acc_size is chosen equal to reg_size .

Parameters

  • reg_size (int) – the registers size

  • acc_size (int) – the accumulator size

  • constant (int) – the constant to add

Warning

Some additional qubits might be allocated by sub-routines inside this routine.

This routine calls:

qat.lang.AQASM.arithmetic.add_mod(reg_size, modulus)

Builds a circuit performing an addition between two numbers modulo a constant modulus. Only the first register is updated during the addition:

\[|a \rangle |b\rangle \mapsto |a \rangle | a + b \mod modulus \rangle\]

Notice that the first register is added into the second register.

Parameters

  • reg_size (int) – the size of the first register

  • modulus (int) – the modulus

Warning

This routine has public arity reg_size but uses 2 additional qubits (these will be automatically allocated at circuit generation time, in the to_circ() method).

This number does not include the optional qubits allocated by sub-routines used inside this routine

This routine calls: