comparator

comparator#

Functionality#

There are a collection of integer comparators that aim to identify the size relation between the decimal value corresponding to a computational basis state and a classical integer.

less_than_phase.py#

Callee: LessThanPhase

Given an integer \(k\) and the \(n\)-qubit computational basis state \(\ket{y}_n\), this phase-version program computes a Boolean function:

\[ \ket{y}_n \mapsto (-1)^{\mathbf{1}(y<k)} \ket{y}_n = e^{i \pi \mathbf{1}(y<k)} \ket{y}_n. \]

With an event \(A\), the indicator function is defined as:

\[\begin{split} \mathbf{1}(A) \equiv \begin{cases} 1, & A\text{ occurs} \\ 0, & \text{otherwise} \end{cases} \end{split}\]

The input state is defined as \(\ket{y}_n = |q_{n-1} \cdots q_1 q_0\rangle\), where \(y\) is the decimal value of the binary string \(q_{n-1} \cdots q_0\).

Note:

To ensure the intended functionality, \(k\) must satisfy \(0 \le k < 2^n\).

Test expectations:

The comparison result is encoded as a phase flip on the corresponding basis state of \(y\). It is a global phase, which can be directly inspected on a statevector-based backend, but not directly observable by measurement.

Doc references: [5]

less_than_qubit.py#

Callee: LessThanQubit

The qubit version of the less-than comparison stores the comparison result in an additional qubit:

\[ |x\rangle_1 \ket{y}_n \mapsto |x \oplus \mathbf{1}(y<k)\rangle_1 \ket{y}_n. \]

In the joint state \(\ket{x}_1\ket{y}_n\), \(\ket{x}_1\) refers to the state of the most significant qubit.

Note:

To ensure the intended functionality, \(k\) must satisfy \(0 \le k < 2^n\).

Test expectations:

The comparison result is encoded in the ancilla qubit via XOR and can be obtained directly by measurement. When \(\ket{x}_1\) is initialized as \(\ket{0}\), it becomes \(\ket{\mathbf{1}(y<k)}\).

Doc references: [5]

integer_comparator_greedy.py#

Callee: IntegerComparatorGreedy

Perform a \(\ge\) (or \(<\)) on a qubit register against a classical integer.

\[\begin{split} \ket{0}_1 \ket{y}_n \mapsto \begin{cases} \ket{\mathbf{1}(y \ge k)}_1 \ket{y}_n, & \text{geq is true} \\ \ket{\mathbf{1}(y < k)}_1 \ket{y}_n, & \text{geq is false} \end{cases}. \end{split}\]

Test expectations:

The comparison result is encoded in one ancilla qubit and can be obtained directly by measurement.

Doc references: [6]

integer_comparator_old.py#

Callee: IntegerComparatorOld

This is the deprecated old version of integer_comparator_greedy, while it has been used for an empirical study on quantum software testing [7].

\[\begin{split} \ket{0}_n \ket{y}_n \mapsto \begin{cases} \ket{\mathbf{1}(y \ge k)}_n \ket{y}_n, & \text{geq is true} \\ \ket{\mathbf{1}(y < k)}_n \ket{y}_n, & \text{geq is false} \end{cases}. \end{split}\]

Compared to integer_comparator_greedy, the old version employs \(n\) qubits to restore the final result.

Test expectations:

The comparison result is encoded in \(n\) ancilla qubits and can be obtained directly by measurement.

Doc references: [6] [7]

API#

qolumbina.programs.comparator.integer_comparator_greedy#

class IntegerComparatorGreedy(num_state_qubits, value, geq=True, label=None)[source]#

Bases: QuantumCircuit

Perform a \(\geq\) (or \(<\)) on a qubit register against a classical integer.

This operator compares basis states \(|i\rangle_n\) against a classically given integer \(L\) of fixed value and flips a target qubit if \(i \geq L\) (or \(<\) depending on the parameter geq):

\[|i\rangle_n |0\rangle \mapsto |i\rangle_n |i \geq L\rangle\]
Parameters:

  • num_state_qubits (int) – The number of qubits in the registers.

  • value (int) – The value \(L\) to compre to.

  • geq (bool) – If True compute \(i \geq L\), otherwise compute \(i < L\).

  • label (str | None) – An optional label for the gate.

synth_integer_comparator_greedy(num_state_qubits, value, geq=True)[source]#

Implement an integer comparison based on value-by-value comparison.

For value smaller than 2 ** (num_state_qubits - 1) this circuit implements value multi-controlled gates with control states 0, 1, …, value - 1, such that the target qubit is flipped if the qubit state represents any of the allowed values. For value larger than that, geq is flipped. This implementation can require an exponential number of gates. If auxiliary qubits are available, the implementation provided by synth_integer_comparator_2s() is more efficient.

Parameters:

  • num_state_qubits (int) – The number of qubits encoding the value to compare to.

  • value (int) – The value to compare to.

  • geq (bool) – If True flip the target bit if the qubit state is \(\geq\) than the value, otherwise implement \(<\).

Returns:

A circuit implementing the integer comparator.

Return type:

QuantumCircuit

qolumbina.programs.comparator.integer_comparator_old#

class IntegerComparatorOld(num_state_qubits=None, value=None, geq=True, name='cmp')[source]#

Bases: QuantumCircuit

Operator compares basis states \(|i\rangle_n\) against a classically given integer \(L\) of fixed value and flips a target qubit if \(i \geq L\) (or \(<\) depending on the parameter geq):

\[|i\rangle_n |0\rangle \mapsto |i\rangle_n |i \geq L\rangle\]

This operation is based on two’s complement implementation of binary subtraction but only uses carry bits and no actual result bits. If the most significant carry bit (the results bit) is 1, the \(\geq\) condition is True otherwise it is False.

Create a new fixed value comparator circuit.

Parameters:

  • num_state_qubits (int | None) – Number of state qubits \(n\). If this is set it will determine the number of qubits required for the circuit.

  • value (int | None) – The fixed value \(L\) to compare with.

  • geq (bool) – If True, evaluate a >= condition, else <.

  • name (str) – Name of the circuit.

property geq: bool#

Return whether the comparator compares greater or less equal.

Returns:

True, if the comparator compares >=, False if <.

property num_ancilla_qubits#

Deprecated. Use num_ancillas instead.

property num_state_qubits: int#

The number of qubits encoding the state for the comparison.

Returns:

The number of state qubits.

property value: int#

The value to compare the qubit register to.

Returns:

The value against which the value of the qubit register is compared.

qolumbina.programs.comparator.less_than_phase#

class LessThanPhase(input_qubits, integer, name=None)[source]#

Bases: QuantumCircuit

Less-than comparator oracle (phase version).

Acts on \(n\) qubits and applies a phase flip when \(x < m\).

Parameters:

  • input_qubits (int) – The number of input qubits for comparison, i.e., \(n\).

  • integer (int) – The integer \(k\) to compare with, should be in the range of \([0, 2^n)\).

  • name (str | None) – The name of the circuit.

Raises:

ValueError – If integer is negative or not less than \(2^n\).

qolumbina.programs.comparator.less_than_qubit#

class LessThanQubit(input_qubits, integer, name=None)[source]#

Bases: QuantumCircuit

Less-than comparator oracle (qubit version).

Acts on \(n\) input qubits and 1 target qubit. Flips the target qubit when \(x < m\).

Parameters:

  • input_qubits (int) – The number of input qubits for comparison, i.e., \(n\).

  • integer (int) – The integer \(k\) to compare with, should be in the range of \([0, 2^n)\).

  • name (str | None) – The name of the circuit.

Raises:

ValueError – If integer is negative or not less than \(2^n\).

Contents