braket.experimental.algorithms.quantum_counting.quantum_counting module

Quantum Counting Algorithm implementation using the Amazon Braket SDK.

The quantum counting algorithm combines Grover’s search operator with Quantum Phase Estimation (QPE) to count the number of marked items in an unstructured search space of N = 2^n elements.

Reference:

G. Brassard, P. Høyer, and A. Tapp, “Quantum Counting”, Proceedings of ICALP 1998. arXiv:quant-ph/9805082

braket.experimental.algorithms.quantum_counting.quantum_counting.build_oracle_circuit(n_qubits: int, marked_states: List[int], decompose_ccnot: bool = False) → Circuit[source]

Build an oracle circuit that flips the phase of marked states.

Composes individual oracle circuits from grovers_search.build_oracle for each marked state. Each call flips the phase of one basis state, and their composition marks all specified states.

Parameters:

  • n_qubits (int) – Number of qubits in the search register.

  • marked_states (List[int]) – Indices of marked computational-basis states.

  • decompose_ccnot (bool) – Whether to decompose CCNOT (Toffoli) gates.

Returns:

Circuit – Oracle circuit that flips the phase of all marked states.

Raises:

ValueError – If a marked state index is out of range.

braket.experimental.algorithms.quantum_counting.quantum_counting.build_grover_circuit(n_qubits: int, marked_states: List[int], decompose_ccnot: bool = False) → Circuit[source]

Build the Grover operator G = D · O as a circuit.

Uses circuit primitives from grovers_search: build_oracle for the phase oracle and amplify for the diffusion operator (H · oracle_0 · H).

Parameters:

  • n_qubits (int) – Number of qubits in the search register.

  • marked_states (List[int]) – Indices of marked states.

  • decompose_ccnot (bool) – Whether to decompose CCNOT (Toffoli) gates.

Returns:

Circuit – Circuit implementing the Grover operator G.

braket.experimental.algorithms.quantum_counting.quantum_counting.controlled_grover_circuit(control: int, search_qubits: Qubit | int | Iterable[Qubit | int], marked_states: List[int], power: int = 1, decompose_ccnot: bool = False) → Circuit[source]

Build a controlled Grover operator G^power as a gate-level circuit.

Constructs the controlled Grover operator C-G = C-D · C-O entirely from gate-level primitives:

  • The oracle is made controlled by prepending “1” to each marked-state bitstring, adding the control qubit as an extra MCZ control.

  • The diffusion operator is made controlled by using controlled-H (CH) gates, a controlled zero-oracle, and a Z gate on the control qubit to correct the inherent -1 global phase of the diffusion operator.

Parameters:

  • control (int) – Index of the QPE control qubit.

  • search_qubits (QubitSetInput) – Indices of the search register qubits.

  • marked_states (List[int]) – Indices of marked computational-basis states.

  • power (int) – Number of times to apply the Grover operator (default 1).

  • decompose_ccnot (bool) – Whether to decompose CCNOT (Toffoli) gates.

Returns:

Circuit – Circuit implementing the controlled G^power operator.

braket.experimental.algorithms.quantum_counting.quantum_counting.inverse_qft_for_counting(qubits: Qubit | int | Iterable[Qubit | int]) → Circuit[source]

Inverse Quantum Fourier Transform applied to the given qubits.

Parameters:

qubits (QubitSetInput) – Qubits on which to apply the inverse QFT.

Returns:

Circuit – Circuit implementing the inverse QFT.

braket.experimental.algorithms.quantum_counting.quantum_counting.quantum_counting_circuit(counting_circ: Circuit, counting_qubits: Qubit | int | Iterable[Qubit | int], search_qubits: Qubit | int | Iterable[Qubit | int], marked_states: List[int], decompose_ccnot: bool = False) → Circuit[source]

Create the full quantum counting circuit with result types.

Builds the controlled Grover operator as a gate-level circuit and applies QPE.

Parameters:

  • counting_circ (Circuit) – Initial circuit (may contain setup operations).

  • counting_qubits (QubitSetInput) – Qubits for the counting (precision) register.

  • search_qubits (QubitSetInput) – Qubits for the search register.

  • marked_states (List[int]) – Indices of marked computational-basis states.

  • decompose_ccnot (bool) – Whether to decompose CCNOT (Toffoli) gates.

Returns:

Circuit – The complete quantum counting circuit with result types.

braket.experimental.algorithms.quantum_counting.quantum_counting.quantum_counting(counting_qubits: Qubit | int | Iterable[Qubit | int], search_qubits: Qubit | int | Iterable[Qubit | int], marked_states: List[int], decompose_ccnot: bool = False) → Circuit[source]

Build the core quantum counting circuit using QPE on the Grover operator.

Constructs the controlled Grover operator as a gate-level circuit from grovers_search primitives (build_oracle for the phase oracle and controlled-H gates for the diffusion operator).

The circuit structure:

  1. Apply H to all counting qubits

  2. Apply H to all search qubits (prepare uniform superposition |s⟩)

  3. Apply controlled-G^(2^k) for each counting qubit k

  4. Apply inverse QFT to counting qubits

Parameters:

  • counting_qubits (QubitSetInput) – Qubits for the counting (precision) register.

  • search_qubits (QubitSetInput) – Qubits for the search register.

  • marked_states (List[int]) – Indices of marked computational-basis states.

  • decompose_ccnot (bool) – Whether to decompose CCNOT (Toffoli) gates.

Returns:

Circuit – Circuit implementing the quantum counting algorithm.

braket.experimental.algorithms.quantum_counting.quantum_counting.run_quantum_counting(circuit: Circuit, device: Device, shots: int = 1000) → QuantumTask[source]

Run the quantum counting circuit on a device.

Parameters:

  • circuit (Circuit) – The quantum counting circuit to run.

  • device (Device) – Braket device backend.

  • shots (int) – Number of measurement shots (default is 1000).

Returns:

QuantumTask – Task from running quantum counting.

braket.experimental.algorithms.quantum_counting.quantum_counting.get_quantum_counting_results(task, counting_qubits: Qubit | int | Iterable[Qubit | int], search_qubits: Qubit | int | Iterable[Qubit | int], verbose: bool = False) → Dict[str, Any][source]

Post-process quantum counting results to estimate the number of marked items.

After measuring the counting qubits, the most likely outcome y gives an estimate of the phase φ = y / 2^t. The number of marked items M is:

M = N · sin²(π · φ)

where N = 2^n_search.

Parameters:

  • task (QuantumTask) – The task holding quantum counting results.

  • counting_qubits (QubitSetInput) – Qubits of the counting register.

  • search_qubits (QubitSetInput) – Qubits of the search register.

  • verbose (bool) – If True, print detailed results (default False).

Returns:

Dict[str, Any] –

Aggregate measurement results including:

  • measurement_counts: raw measurement counts

  • counting_register_results: counts collapsed to the counting register

  • phases: estimated phases φ for each measured bitstring

  • estimated_counts: estimated M for each measured bitstring

  • best_estimate: best estimate of M (from most frequent outcome)

  • search_space_size: N = 2^n_search