quantum_multiplier

Functionality

This program familily provides quantum circuits to perform multiplication of two quantum registers using different designs and implementations.

---

multiplier_qft.py

Callee: Multiplier

Compute the product of two equally sized qubit registers into a new register.

For two input registers \(\ket{a}_n\), \(\ket{b}_n\) with \(n\) qubits each and an output register with \(2n\) qubits, a multiplier performs the following operation

\[ \ket{0}_t \ket{b}_n \ket{a}_n \mapsto \ket{a \cdot b}_t \ket{b}_n \ket{a}_n, \]

where \(t\) is the number of qubits used to represent the result. To completely store the result of the multiplication without overflow we need \(t=2n\) qubits.

The quantum register \(\ket{a}_n\) (analogously \(\ket{b}_n\) and output register) is defined as

\[ \ket{a}_n \equiv \ket{a_{n-1}} \otimes \ket{a_{n-2}} \otimes \cdots \otimes \ket{a_0}, \]

for \(a_i\in\{0,1\}\), is associated with the integer value

\[ a = 2^0 a_0 + 2^1 a_1 + \cdots + 2^{n-1} a_{n-1}. \]

Test expectations:

The results are stored in the \(2n\)-qubit output register, making the probability of the corresponding basis state 1 by measurement.

Doc reference: [42]

---

multiplier_hrs.py

Callee: MultiplierHRS

Given the total number of qubits \(n\), this circuit computes the product of two equally sized qubit registers using the Häner-Roetteler-Svore (HRS) method, where \(m = \left\lfloor n/4 \right\rfloor\).

According to the default kind as half in the current version, half adders are used in the HRS multiplier design. The relation between indices and registers is as follows:

Index	\(0 \sim (m-1)\)	\(m \sim (2m-1)\)	\(2m \sim (4m-1)\)	\(4m\)	\(4m+1\)
Register	a[0 … m−1]	b[0 … m−1]	out[0 … 2m−1]	cout[0]	help[0]

In this case, cout is used to handle any overflow during addition. The mapping performed by the circuit is as follows:

\[ \ket{0}_1 \ket{\text{cout}}_1 \ket{0}_{2m} \ket{b}_m \ket{a}_m \mapsto \ket{0}_1 \ket{0}_1 \ket{a \cdot b}_{2m} \ket{b}_m \ket{a}_m. \]

Herein, \(\text{cout} = \left\lfloor (a\cdot b) / 2^{2m} \right\rfloor\). Note that \(0 \le a, b \le 2^m - 1\), and \(a \cdot b \le (2^m-1)^2 = 2^{2m} - 2^{m+1} + 1 < 2^{2m}\). Hence, we have \(\text{cout} = 0\) for any \(a\) and \(b\) with current length of qubits.

Test expectations:

The results are stored in the \(2m\)-qubit output register, making the probability of the corresponding basis state 1 by measurement.

Technical Debt for Development

The kind parameter in MultiplierHRS class and related test cases have been retained for future extensions but are currently not in active use. According to the functionality of _adder_ripple_c04 from Qiskit, we expect that

• For kind="full", Uses full adders in the HRS multiplier design. The relation between indices and registers is as follows:

  Index	\(0 \sim (m-1)\)	\(m \sim (2m-1)\)	\(2m \sim (4m-1)\)	\(4m\)	\(4m+1\)
  Register	a[0 … m−1]	b[0 … m−1]	out[0 … 2m−1]	cin[0]	cout[0]

  In this case, cin is used to handle any overflow during addition. Hence, the mapping performed by the circuit is as follows:

  \[ \ket{\text{cout}}_1 \ket{\text{cin}}_1 \ket{0}_{2m} \ket{b}_m \ket{a}_m \mapsto \ket{0}_1 \ket{\text{cin}}_1 \ket{a \cdot b + \text{cin}}_{2m} \ket{b}_m \ket{a}_m. \]

  The registers pad are auxiliary qubits that are not used in the computation and remain in the \(\ket{0}\) state. The register cin allows adding an initial carry-in value to the multiplication result, where \(\text{cin} \in \{0,1\}\). The register cout captures any overflow that may occur during the addition process. Similarly, \(a \cdot b + \text{cin} < 2^{2m}\), hence, we have \(\text{cout} = 0\) for any \(a\) and \(b\) with current length of qubits.

• For kind="fixed", Uses a fixed-width adder in the HRS multiplier design. The relation between indices and registers is as follows:

  Index	\(0 \sim (m-1)\)	\(m \sim (2m-1)\)	\(2m \sim (4m-1)\)	\(4m\)	\(4m+1\)
  Register	a[0 … m−1]	b[0 … m−1]	out[0 … 2m−1]	cin[0]	cout[0]

  In comparison, there is no cout register to handle overflow during addition. Hence, the mapping performed by the circuit is as follows:

  \[ \ket{0}_1\ket{0}_{2m} \ket{a}_m \ket{b}_m \mapsto \ket{0}_1 \ket{(a \cdot b) \mod 2^{2m}}_{2m} \ket{b}_m \ket{a}_m. \]

  Even though, we have \( (a \cdot b) \mod 2^{2m} = a \cdot b\), for any \(a\) and \(b\) with current length of qubits.

However, the original code from munich-quantum-toolkit/bench can support half only. Besides, it is not easy to extend such a kind without bugs. Therefore, the test cases for full and fixed kinds have been commented out for now.

API

qolumbina.programs.quantum_multiplier.multiplier_hrs

HRS Cumulative Multiplier.

class MultiplierHRS(num_qubits, name=None)

Bases: QuantumCircuit

Create a Haener-Roetteler-Svore (HRS) cumulative multiplier circuit.

The principle of the HRS cumulative multiplier is based on performing a sequence of controlled additions of shifted versions of the multiplicand into an accumulator register, conditioned on the bits of the multiplier.

See also

qiskit.circuit.library.HRSCumulativeMultiplier

Parameters:

• num_qubits (int) – The total number of qubits in the circuit, i.e., \(n\), including the two input registers \(\ket{a}\), \(\ket{b}\) and the output register \(\ket{out}\).

• name (str | None)

Note

1. The number of qubits in each input register is determined by \(m = \left\lfloor n/4 \right\rfloor\), and the output register has \(2m\) qubits. The remaining qubits are used as carry and helper qubits for the addition operations.

2. As a technical debt, we temporarily do not support different kinds of adders in the HRS multiplier. For future development, the kind of adder to be used in the multiplier, can be "full", "half", or "fixed".

adder_ripple_c04(num_state_qubits, kind='half')

A ripple-carry circuit to perform in-place addition on two qubit registers.

This circuit uses \(2n + O(1)\) CCX gates and \(5n + O(1)\) CX gates, at a depth of \(2n + O(1)\) [1]. The constant depends on the kind of adder implemented.

As an example, a full ripple-carry adder on 3-qubit registers applies a MAJ cascade from the least significant bit to the most significant bit, then an UMA cascade in reverse order to uncompute the carries and write the sum.

Here MAJ and UMA gates correspond to the gates introduced in [1]. Note that in this implementation the input register qubits are ordered as all qubits from the first input register, followed by all qubits from the second input register.

Two different kinds of adders are supported. By setting the kind argument, you can also choose a half-adder, which doesn’t have a carry-in, and a fixed-sized-adder, which has neither carry-in nor carry-out, and thus acts on fixed register sizes. Unlike the full-adder, these circuits need one additional helper qubit.

For the fixed-sized adder (kind="fixed"), the same MAJ/UMA structure is used without a carry-in or carry-out wire.

It has one less qubit than the full-adder since it doesn’t have the carry-out, but uses a helper qubit instead of the carry-in, so it only has one less qubit, not two.

Parameters:

• num_state_qubits (int) – The number of qubits in either input register for state \(|a\rangle\) or \(|b\rangle\). The two input registers must have the same number of qubits.

• kind (str) – The kind of adder, can be "full" for a full adder, "half" for a half adder, or "fixed" for a fixed-sized adder. A full adder includes both carry-in and carry-out, a half only carry-out, and a fixed-sized adder neither carry-in nor carry-out.

Raises:

ValueError – If num_state_qubits is lower than 1.

Return type:

QuantumCircuit

References:

[1] Cuccaro et al., A new quantum ripple-carry addition circuit, 2004. arXiv:quant-ph/0410184

[2] Vedral et al., Quantum Networks for Elementary Arithmetic Operations, 1995. arXiv:quant-ph/9511018

create_circuit(num_qubits, kind)

Create a hrs cumulative multiplier circuit.

Parameters:

• num_qubits (int) – Number of qubits of the returned quantum circuit, (num_qubits - 1) must be divisible by 4.

• kind (str)

Returns:

The constructed hrs cumulative multiplier circuit.

Return type:

QuantumCircuit

See also

qiskit.circuit.library.HRSCumulativeMultiplier

qolumbina.programs.quantum_multiplier.multiplier_qft

Compute the product of two equally sized qubit registers.

class MultiplierQFT(num_state_qubits, num_result_qubits=None, label=None)

Bases: QuantumCircuit

Compute the product of two equally sized qubit registers into a new register.

For two input registers \(|a\rangle_n\), \(|b\rangle_n\) with \(n\) qubits each and an output register with \(2n\) qubits, a multiplier performs the following operation

\[|a\rangle_n |b\rangle_n |0\rangle_{t} \mapsto |a\rangle_n |b\rangle_n |a \cdot b\rangle_t\]

where \(t\) is the number of bits used to represent the result. To completely store the result of the multiplication without overflow we need \(t = 2n\) bits.

The quantum register \(|a\rangle_n\) (analogously \(|b\rangle_n\) and output register)

\[|a\rangle_n = |a_0\rangle \otimes \cdots \otimes |a_{n - 1}\rangle,\]

for \(a_i \in \{0, 1\}\), is associated with the integer value

\[a = 2^{0}a_{0} + 2^{1}a_{1} + \cdots + 2^{n - 1}a_{n - 1}.\]

Parameters:

• num_state_qubits (int) – The number of qubits (\(n\)) in each of the input registers.

• num_result_qubits (int | None) – The number of result qubits (\(t\)) to limit the output to. The default value is None. If None, defaults to 2 * num_state_qubits to represent any possible result from the multiplication of the two inputs.

• name – The name of the circuit.

• label (str | None)

Raises:

• ValueError – If num_state_qubits is smaller than 1.

• ValueError – If num_result_qubits is smaller than num_state_qubits.

• ValueError – If num_result_qubits is larger than 2 * num_state_qubits.

property num_result_qubits: int

The number of result qubits to limit the output to.

Returns:

The number of result qubits.

property num_state_qubits: int

The number of state qubits, i.e. the number of bits in each input register.

Returns:

The number of state qubits.