libs.math
A tiny math library which will be extended thoughout the next weeks. Right now, it only contains the math functions necessary to run Beauregard’s implementation of Shor’s algorithm.
Module containing constant math quantum operations. |
|
Registers a few default replacement rules for Shor's algorithm to work (see Examples). |
|
Quantum number math gates for ProjectQ. |
|
Definition of some mathematical quantum operations. |
|
Add a constant to a quantum number represented by a quantum register, stored from low- to high-bit. |
|
Add a constant to a quantum number represented by a quantum register modulo N. |
|
|
Built-in mutable sequence. |
Multiply a quantum number represented by a quantum register by a constant modulo N. |
|
Subtract a constant from a quantum number represented by a quantum register, stored from low- to high-bit. |
|
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.
_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.
- 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
- 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
- class projectq.libs.math._gates.ComparatorQuantumGate[source]
Flip a compare qubit if the binary value of first imput 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
- 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>
- 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
- 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
_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>
(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.,
|remainder>|quotient>|divisor> -> |dividend>|remainder(0)>|divisor>
- 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,
(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.,
|dividend>|remainder>|divisor> -> |remainder>|quotient>|divisor>
(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,
(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.,
(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
- 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.
- 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.
- 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