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.
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
- 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 theto_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:
mult_const_mod()
with arguments (acc_size, acc_size + 1, _, _)
- 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()
with arguments (acc_size, _, _)
- 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:
- Any addition by a constant (E.g:
qat.lang.AQASM.qftarith.add_const()
or qat.lang.AQASM.classarith.add_const()
) with arguments (reg_size) and (reg_size + 1)
- Any addition by a constant (E.g:
- 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:
- Any addition by a constant (E.g:
qat.lang.AQASM.qftarith.add_const()
or
qat.lang.AQASM.classarith.add_const()
) with arguments (acc_size )
- Any addition by a constant (E.g:
- 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:
- Any addition (E.g:
qat.lang.AQASM.qftarith.add()
or qat.lang.AQASM.classarith.add()
) with arguments (reg_size`+ 1, `reg_size )
- Any addition (E.g:
Any addition of a constant (E.g
qat.lang.AQASM.qftarith.add_const()
)