libs.math

A tiny math library which will be extended throughout the next weeks. Right now, it only contains the math functions necessary to run Beauregard’s implementation of Shor’s algorithm.

`projectq.libs.math._constantmath`	Module containing constant math quantum operations.
`projectq.libs.math._default_rules`	Registers a few default replacement rules for Shor's algorithm to work (see Examples).
`projectq.libs.math._gates`	Quantum number math gates for ProjectQ.
`projectq.libs.math._quantummath`	Definition of some mathematical quantum operations.
`projectq.libs.math.AddConstant`(a)	Add a constant to a quantum number represented by a quantum register, stored from low- to high-bit.
`projectq.libs.math.AddConstantModN`(a, N)	Add a constant to a quantum number represented by a quantum register modulo N.
`projectq.libs.math.all_defined_decomposition_rules`	Built-in mutable sequence.
`projectq.libs.math.MultiplyByConstantModN`(a, N)	Multiply a quantum number represented by a quantum register by a constant modulo N.
`projectq.libs.math.SubConstant`(a)	Subtract a constant from a quantum number represented by a quantum register, stored from low- to high-bit.
`projectq.libs.math.SubConstantModN`(a, N)	Subtract a constant from a quantum number represented by a quantum register modulo N.

Submodules

_constantmath

Module containing constant math quantum operations.

projectq.libs.math._constantmath.add_constant(eng, constant, quint)[source]: Add a classical constant c to the quantum integer (qureg) quint using Draper addition.

Note

Uses the Fourier-transform adder from https://arxiv.org/abs/quant-ph/0008033.

projectq.libs.math._constantmath.add_constant_modN(eng, constant, N, quint)[source]

Add a classical constant c to a quantum integer (qureg) quint modulo N using Draper addition.

This function uses Draper addition and the construction from https://arxiv.org/abs/quant-ph/0205095.

projectq.libs.math._constantmath.inv_mod_N(a, N)[source]: Calculate the inverse of a modulo N.

projectq.libs.math._constantmath.mul_by_constant_modN(eng, constant, N, quint_in)[source]

Multiply a quantum integer by a classical number a modulo N.

i.e.,

|x> -> |a*x mod N>

(only works if a and N are relative primes, otherwise the modular inverse does not exist).

_default_rules

Registers a few default replacement rules for Shor’s algorithm to work (see Examples).

_gates

Quantum number math gates for ProjectQ.

class projectq.libs.math._gates.AddConstant(a)[source]

Add a constant to a quantum number represented by a quantum register, stored from low- to high-bit.

Example

qunum = eng.allocate_qureg(5)  # 5-qubit number
X | qunum[1]  # qunum is now equal to 2
AddConstant(3) | qunum  # qunum is now equal to 5

Important: if you run with conditional and carry, carry needs to be a quantum register for the compiler/decomposition to work.

get_inverse()[source]: Return the inverse gate (subtraction of the same constant).

class projectq.libs.math._gates.AddConstantModN(a, N)[source]

Add a constant to a quantum number represented by a quantum register modulo N.

The number is stored from low- to high-bit, i.e., qunum[0] is the LSB.

Example

qunum = eng.allocate_qureg(5)  # 5-qubit number
X | qunum[1]  # qunum is now equal to 2
AddConstantModN(3, 4) | qunum  # qunum is now equal to 1

Note

Pre-conditions:

c < N
c >= 0
The value stored in the quantum register must be lower than N

get_inverse()[source]: Return the inverse gate (subtraction of the same number a modulo the same number N).

class projectq.libs.math._gates.AddQuantumGate[source]

Add up two quantum numbers represented by quantum registers.

The numbers are stored from low- to high-bit, i.e., qunum[0] is the LSB.

Example

qunum_a = eng.allocate_qureg(5)  # 5-qubit number
qunum_b = eng.allocate_qureg(5)  # 5-qubit number
carry_bit = eng.allocate_qubit()

X | qunum_a[2]  # qunum_a is now equal to 4
X | qunum_b[3]  # qunum_b is now equal to 8
AddQuantum | (qunum_a, qunum_b, carry)
# qunum_a remains 4, qunum_b is now 12 and carry_bit is 0

get_inverse()[source]: Return the inverse gate (subtraction of the same number a modulo the same number N).

get_math_function(qubits)[source]: Get the math function associated with an AddQuantumGate.

class projectq.libs.math._gates.ComparatorQuantumGate[source]

Flip a compare qubit if the binary value of first input is higher than the second input.

The numbers are stored from low- to high-bit, i.e., qunum[0] is the LSB. .. rubric:: Example

qunum_a = eng.allocate_qureg(5)  # 5-qubit number
qunum_b = eng.allocate_qureg(5)  # 5-qubit number
compare_bit = eng.allocate_qubit()
X | qunum_a[4]  # qunum_a is now equal to 16
X | qunum_b[3]  # qunum_b is now equal to 8
ComparatorQuantum | (qunum_a, qunum_b, compare_bit)
# qunum_a and qunum_b remain 16 and 8, qunum_b is now 12 and compare bit is now 1

get_inverse()[source]: Return the inverse of this gate.

class projectq.libs.math._gates.DivideQuantumGate[source]

Divide one quantum number from another.

Takes three inputs which should be quantum registers of equal size; a dividend, a remainder and a divisor. The remainder should be in the state |0…0> and the dividend should be bigger than the divisor.The gate returns (in this order): the remainder, the quotient and the divisor.

The numbers are stored from low- to high-bit, i.e., qunum[0] is the LSB.

Example: .. code-block:: python

qunum_a = eng.allocate_qureg(5) # 5-qubit number qunum_b = eng.allocate_qureg(5) # 5-qubit number qunum_c = eng.allocate_qureg(5) # 5-qubit number

All(X) | [qunum_a[0], qunum_a[3]] # qunum_a is now equal to 9 X | qunum_c[2] # qunum_c is now equal to 4

DivideQuantum | (qunum_a, qunum_b, qunum_c) # qunum_a is now equal to 1 (remainder), qunum_b is now # equal to 2 (quotient) and qunum_c remains 4 (divisor)

# |dividend>|remainder>|divisor> -> |remainder>|quotient>|divisor>

get_inverse()[source]: Return the inverse of this gate.

class projectq.libs.math._gates.MultiplyByConstantModN(a, N)[source]

Multiply a quantum number represented by a quantum register by a constant modulo N.

The number is stored from low- to high-bit, i.e., qunum[0] is the LSB.

Example

qunum = eng.allocate_qureg(5)  # 5-qubit number
X | qunum[2]  # qunum is now equal to 4
MultiplyByConstantModN(3, 5) | qunum  # qunum is now 2.

Note

Pre-conditions:

c < N
c >= 0
gcd(c, N) == 1
The value stored in the quantum register must be lower than N

class projectq.libs.math._gates.MultiplyQuantumGate[source]

Multiply two quantum numbers represented by a quantum registers.

Requires three quantum registers as inputs, the first two are the numbers to be multiplied and should have the same size (n qubits). The third register will hold the product and should be of size 2n+1. The numbers are stored from low- to high-bit, i.e., qunum[0] is the LSB.

Example

qunum_a = eng.allocate_qureg(4)
qunum_b = eng.allocate_qureg(4)
qunum_c = eng.allocate_qureg(9)
X | qunum_a[2]  # qunum_a is now 4
X | qunum_b[3]  # qunum_b is now 8
MultiplyQuantum() | (qunum_a, qunum_b, qunum_c)
# qunum_a remains 4 and qunum_b remains 8, qunum_c is now equal to 32

get_inverse()[source]: Return the inverse of this gate.

projectq.libs.math._gates.SubConstant(a)[source]

Subtract a constant from a quantum number represented by a quantum register, stored from low- to high-bit.

Parameters:: a (int) – Constant to subtract

Example

qunum = eng.allocate_qureg(5)  # 5-qubit number
X | qunum[2]  # qunum is now equal to 4
SubConstant(3) | qunum  # qunum is now equal to 1

projectq.libs.math._gates.SubConstantModN(a, N)[source]

Subtract a constant from a quantum number represented by a quantum register modulo N.

The number is stored from low- to high-bit, i.e., qunum[0] is the LSB.

Parameters:

a (int) – Constant to add
N (int) – Constant modulo which the addition of a should be carried out.

Example

qunum = eng.allocate_qureg(3)  # 3-qubit number
X | qunum[1]  # qunum is now equal to 2
SubConstantModN(4, 5) | qunum  # qunum is now -2 = 6 = 1 (mod 5)

Note

Pre-conditions:

c < N
c >= 0
The value stored in the quantum register must be lower than N

class projectq.libs.math._gates.SubtractQuantumGate[source]

Subtract one quantum number from another quantum number both represented by quantum registers.

Example: .. code-block:: python

qunum_a = eng.allocate_qureg(5) # 5-qubit number qunum_b = eng.allocate_qureg(5) # 5-qubit number X | qunum_a[2] # qunum_a is now equal to 4 X | qunum_b[3] # qunum_b is now equal to 8 SubtractQuantum | (qunum_a, qunum_b) # qunum_a remains 4, qunum_b is now 4

get_inverse()[source]: Return the inverse gate (subtraction of the same number a modulo the same number N).

_quantummath

Definition of some mathematical quantum operations.

projectq.libs.math._quantummath.add_quantum(eng, quint_a, quint_b, carry=None)[source]

Add two quantum integers.

i.e.,

|a0…a(n-1)>|b(0)…b(n-1)>|c> -> |a0…a(n-1)>|b+a(0)…b+a(n)>

(only works if quint_a and quint_b are the same size and carry is a single qubit)

Parameters:

eng (MainEngine) – ProjectQ MainEngine
quint_a (list) – Quantum register (or list of qubits)
quint_b (list) – Quantum register (or list of qubits)
carry (list) – Carry qubit

Notes

Ancilla: 0, size: 7n-6, toffoli: 2n-1, depth: 5n-3.

References

Quantum addition using ripple carry from: https://arxiv.org/pdf/0910.2530.pdf

projectq.libs.math._quantummath.comparator(eng, quint_a, quint_b, comp)[source]

Compare the size of two quantum integers.

i.e,

if a>b: |a>|b>|c> -> |a>|b>|c+1>

else: |a>|b>|c> -> |a>|b>|c>

(only works if quint_a and quint_b are the same size and the comparator is 1 qubit)

Parameters:

eng (MainEngine) – ProjectQ MainEngine
quint_a (list) – Quantum register (or list of qubits)
quint_b (list) – Quantum register (or list of qubits)
comp (Qubit) – Comparator qubit

Notes

Comparator flipping a compare qubit by computing the high bit of b-a, which is 1 if and only if a > b. The high bit is computed using the first half of circuit in AddQuantum (such that the high bit is written to the carry qubit) and then undoing the first half of the circuit. By complementing b at the start and b+a at the end the high bit of b-a is calculated.

Ancilla: 0, size: 8n-3, toffoli: 2n+1, depth: 4n+3.

projectq.libs.math._quantummath.inverse_add_quantum_carry(eng, quint_a, quint_b)[source]

Inverse of quantum addition with carry.

Parameters:

eng (MainEngine) – ProjectQ MainEngine
quint_a (list) – Quantum register (or list of qubits)
quint_b (list) – Quantum register (or list of qubits)

projectq.libs.math._quantummath.inverse_quantum_division(eng, remainder, quotient, divisor)[source]

Perform the inverse of a restoring integer division.

i.e.,

Parameters:

eng (MainEngine) – ProjectQ MainEngine
dividend (list) – Quantum register (or list of qubits)
remainder (list) – Quantum register (or list of qubits)
divisor (list) – Quantum register (or list of qubits)

projectq.libs.math._quantummath.inverse_quantum_multiplication(eng, quint_a, quint_b, product)[source]

Inverse of the multiplication of two quantum integers.

i.e,

|a>|b>|a*b> -> |a>|b>|0>

(only works if quint_a and quint_b are of the same size, n qubits and product has size 2n+1)

Parameters:

eng (MainEngine) – ProjectQ MainEngine
quint_a (list) – Quantum register (or list of qubits)
quint_b (list) – Quantum register (or list of qubits)
product (list) – Quantum register (or list of qubits) storing the result

projectq.libs.math._quantummath.quantum_conditional_add(eng, quint_a, quint_b, conditional)[source]

Add up two quantum integers if conditional is high.

i.e.,

|a>|b>|c> -> |a>|b+a>|c> (without a carry out qubit)

if conditional is low, no operation is performed, i.e., |a>|b>|c> -> |a>|b>|c>

Parameters:

eng (MainEngine) – ProjectQ MainEngine
quint_a (list) – Quantum register (or list of qubits)
quint_b (list) – Quantum register (or list of qubits)
conditional (list) – Conditional qubit

Notes

Ancilla: 0, Size: 7n-7, Toffoli: 3n-3, Depth: 5n-3.

References

Quantum Conditional Add from https://arxiv.org/pdf/1609.01241.pdf

projectq.libs.math._quantummath.quantum_conditional_add_carry(eng, quint_a, quint_b, ctrl, z)[source]

Add up two quantum integers if the control qubit is |1>.

i.e.,

|a>|b>|ctrl>|z(0)z(1)> -> |a>|s(0)…s(n-1)>|ctrl>|s(n)z(1)> (where s denotes the sum of a and b)

If the control qubit is |0> no operation is performed:

|a>|b>|ctrl>|z(0)z(1)> -> |a>|b>|ctrl>|z(0)z(1)>

(only works if quint_a and quint_b are of the same size, ctrl is a single qubit and z is a quantum register with 2 qubits.

Parameters:

eng (MainEngine) – ProjectQ MainEngine
quint_a (list) – Quantum register (or list of qubits)
quint_b (list) – Quantum register (or list of qubits)
ctrl (list) – Control qubit
z (list) – Quantum register with 2 qubits

Notes

Ancilla: 2, size: 7n - 4, toffoli: 3n + 2, depth: 5n.

References

Quantum conditional add with no input carry from: https://arxiv.org/pdf/1706.05113.pdf

projectq.libs.math._quantummath.quantum_division(eng, dividend, remainder, divisor)[source]

Perform restoring integer division.

i.e.,

(only works if all three qubits are of equal length)

Parameters:

eng (MainEngine) – ProjectQ MainEngine
dividend (list) – Quantum register (or list of qubits)
remainder (list) – Quantum register (or list of qubits)
divisor (list) – Quantum register (or list of qubits)

Notes

Ancilla: n, size 16n^2 - 13, toffoli: 5n^2 -5 , depth: 10n^2-6.

References

Quantum Restoring Integer Division from: https://arxiv.org/pdf/1609.01241.pdf.

projectq.libs.math._quantummath.quantum_multiplication(eng, quint_a, quint_b, product)[source]

Multiplies two quantum integers.

i.e,

|a>|b>|0> -> |a>|b>|a*b>

(only works if quint_a and quint_b are of the same size, n qubits and product has size 2n+1).

Parameters:

eng (MainEngine) – ProjectQ MainEngine
quint_a (list) – Quantum register (or list of qubits)
quint_b (list) – Quantum register (or list of qubits)
product (list) – Quantum register (or list of qubits) storing the result

Notes

Ancilla: 2n + 1, size: 7n^2 - 9n + 4, toffoli: 5n^2 - 4n, depth: 3n^2 - 2.

References

Quantum multiplication from: https://arxiv.org/abs/1706.05113.

projectq.libs.math._quantummath.subtract_quantum(eng, quint_a, quint_b)[source]

Subtract two quantum integers.

i.e.,

|a>|b> -> |a>|b-a>

(only works if quint_a and quint_b are the same size)

Parameters:

eng (MainEngine) – ProjectQ MainEngine
quint_a (list) – Quantum register (or list of qubits)
quint_b (list) – Quantum register (or list of qubits)

Notes

Quantum subtraction using bitwise complementation of quantum adder: b-a = (a + b’)’. Same as the quantum addition circuit except that the steps involving the carry qubit are left out and complement b at the start and at the end of the circuit is added.

Ancilla: 0, size: 9n-8, toffoli: 2n-2, depth: 5n-5.

References

Quantum addition using ripple carry from: https://arxiv.org/pdf/0910.2530.pdf

Module contents

Math gate definitions.

class projectq.libs.math.AddConstant(a)[source]

Add a constant to a quantum number represented by a quantum register, stored from low- to high-bit.

Example

qunum = eng.allocate_qureg(5)  # 5-qubit number
X | qunum[1]  # qunum is now equal to 2
AddConstant(3) | qunum  # qunum is now equal to 5

Important: if you run with conditional and carry, carry needs to be a quantum register for the compiler/decomposition to work.

__init__(a)[source]

Initialize the gate to the number to add.

Parameters:: a (int) – Number to add to a quantum register.

It also initializes its base class, BasicMathGate, with the corresponding function, so it can be emulated efficiently.

get_inverse()[source]: Return the inverse gate (subtraction of the same constant).

class projectq.libs.math.AddConstantModN(a, N)[source]

Add a constant to a quantum number represented by a quantum register modulo N.

The number is stored from low- to high-bit, i.e., qunum[0] is the LSB.

Example

qunum = eng.allocate_qureg(5)  # 5-qubit number
X | qunum[1]  # qunum is now equal to 2
AddConstantModN(3, 4) | qunum  # qunum is now equal to 1

Note

Pre-conditions:

c < N
c >= 0
The value stored in the quantum register must be lower than N

__init__(a, N)[source]

Initialize the gate to the number to add modulo N.

Parameters:

a (int) – Number to add to a quantum register (0 <= a < N).
N (int) – Number modulo which the addition is carried out.

It also initializes its base class, BasicMathGate, with the corresponding function, so it can be emulated efficiently.

get_inverse()[source]: Return the inverse gate (subtraction of the same number a modulo the same number N).

class projectq.libs.math.MultiplyByConstantModN(a, N)[source]

Multiply a quantum number represented by a quantum register by a constant modulo N.

The number is stored from low- to high-bit, i.e., qunum[0] is the LSB.

Example

qunum = eng.allocate_qureg(5)  # 5-qubit number
X | qunum[2]  # qunum is now equal to 4
MultiplyByConstantModN(3, 5) | qunum  # qunum is now 2.

Note

Pre-conditions:

c < N
c >= 0
gcd(c, N) == 1
The value stored in the quantum register must be lower than N

__init__(a, N)[source]

Initialize the gate to the number to multiply with modulo N.

Parameters:

a (int) – Number by which to multiply a quantum register (0 <= a < N).
N (int) – Number modulo which the multiplication is carried out.

It also initializes its base class, BasicMathGate, with the corresponding function, so it can be emulated efficiently.

projectq.libs.math.SubConstant(a)[source]

Subtract a constant from a quantum number represented by a quantum register, stored from low- to high-bit.

Parameters:: a (int) – Constant to subtract

Example

qunum = eng.allocate_qureg(5)  # 5-qubit number
X | qunum[2]  # qunum is now equal to 4
SubConstant(3) | qunum  # qunum is now equal to 1

projectq.libs.math.SubConstantModN(a, N)[source]

Subtract a constant from a quantum number represented by a quantum register modulo N.

The number is stored from low- to high-bit, i.e., qunum[0] is the LSB.

Parameters:

a (int) – Constant to add
N (int) – Constant modulo which the addition of a should be carried out.

Example

qunum = eng.allocate_qureg(3)  # 3-qubit number
X | qunum[1]  # qunum is now equal to 2
SubConstantModN(4, 5) | qunum  # qunum is now -2 = 6 = 1 (mod 5)

Note

Pre-conditions:

c < N
c >= 0
The value stored in the quantum register must be lower than N