workbench_algorithms.subroutines.hamming_weight

Main functions to compute the hamming weight of a register.

ComputeHammingWeightNaive

ComputeHammingWeightNaive(adder=GidneyAdd(), **kwargs)

Bases: Qubrick

Naive/Qubit-efficient circuit to compute the Hamming Weight of a quantum register.

This Qubrick computes the hamming weight of a quantum register (coherently). The structure of this algorithm is to initialize a register of size log(N + 1) for an N qubit register and then traverse serially through the qubits in the target register and perform controlled adders onto the newly allocated ancilla register such that the value of the qubit in the target register is added into the value of the hamming weight register.

Parameters:

Name	Type	Description	Default
adder	Qubrick	Qubrick to perform a quantum adder.	GidneyAdd()
**kwargs	dict[str, Any]	Other arguments to pass to the init.	{}

compute

compute(target_register: Qubits, ctrl: Qubits | int = 0)

Compute the Hamming Weight.

Parameters:

Name	Type	Description	Default
target_register	Qubits	The target qubit register to compute the hamming weight of.	required
ctrl	Qubits or int	Quantum control conditions	0

Note

• Allocates a quantum register storing the hamming weight

ComputeHammingWeightGroupOfThrees

ComputeHammingWeightGroupOfThrees(
    use_black_box: bool = False, **kwargs
)

Bases: Qubrick

Quantum circuit to compute the Hamming Weight of a quantum register that uses roughly N ancillae and O(N) Toff.

This Qubrick computes the hamming weight of a quantum register (coherently). This is a recursive algorithm that groups qubits into batches of the 3 and computes the hamming weight of these qubits. The carry bit in this output is upgraded to the "next level" while the low-bit is tossed back into the current group of qubits. This process is repeated until all low-bits at the current level have been added and we are left with only one bit - this becomes the low bit in our hamming weight register. The process is then repeated on all of the carry bits that were upgraded to the "next level". This process is repeated until there are no more carry bits that get upgraded. This algorithm is described in arXiv:1709.06648.

compute

compute(target_register: Qubits, ctrl: Qubits | int = 0)

Compute the Hamming Weight.

Parameters:

Name	Type	Description	Default
target_register	Qubits	The target qubit register to compute the hamming weight of.	required
ctrl	Qubits or int	Quantum control conditions	0

Note

• Allocates a quantum register storing the hamming weight
• If qubrick is controlled and the user wants black box cost, then the black box cost will be just naively counted from operations

ComputeHammingWeightBinaryRecursion

ComputeHammingWeightBinaryRecursion(adder=None, **kwargs)

Bases: Qubrick

Quantum circuit to compute the Hamming Weight of a register that uses roughly O(N/2) ancillae and O(N) Toffoli.

This Qubrick computes the hamming weight of a quantum register (coherently) based on the algorithm outlined in this paper: Boyar, Joan, and René Peralta. "The exact multiplicative complexity of the Hamming weight function." This is a truly recursive algorithm that computes the hamming weight of a register by splitting it into three separate registers: U, V, and M. The third register, M, is of size 1 and is just an arbitrary qubit in the original register. Reigsters U and V are then an even split of qubits in the original register excluding the M qubit. The hamming weight is then computed as H(U) + H(V) + M where H(U) and H(V) are the hamming weight of U and V which are computed by calling the hamming weight computation function recursively.

Parameters:

Name	Type	Description	Default
adder	Qubrick	Qubrick to perform a quantum adder.	None
**kwargs	dict[str, Any]	Other arguments to pass to the init.	{}

compute

compute(target_register: Qubits, ctrl: Qubits | int = 0)

Compute the Hamming Weight.

Parameters:

Name	Type	Description	Default
target_register	Qubits	The target qubit register to compute the hamming weight of.	required
ctrl	Qubits or int	Quantum control conditions	0

Note

• Allocates a quantum register storing the hamming weight