org.soulspace.qclojure.application.algorithm.grover — org.soulspace/qclojure 0.1.0

Grover's Search Algorithm

Grover's algorithm provides a quadratic speedup for searching unsorted databases. For N items, classical search requires O(N) queries, while Grover's requires O(√N). The number of Grover iterations is approximately π√N/4, where N is the size of the search space.

This implementation builds the quantum circuit for Grover's algorithm and executes it on a specified quantum backend.

The algorithm consists of:

1. Initializing a uniform superposition state |+⟩^⊗n
2. Repeating Grover iterations: a. Apply the oracle Uf to mark target states b. Apply the diffusion operator (inversion about average)
3. Measuring the final state to find the target item with high probability

The oracle function should take a computational basis state index and return true for target states.

The diffusion operator applies inversion about the average amplitude.

add-oracle-fn clj

(add-oracle-fn oracle-fn n-qubits)

Build the quantum circuit for Grover's oracle Uf.

Implements a phase oracle that flips the phase of target computational basis states. For each target state, it applies controlled gates to flip the phase when the qubits match the binary representation of the target state index.

Parameters:

• oracle-fn: Function that takes a basis state index and returns true if it's a target state Represents the Grover oracle Uf
• n-qubits: Number of qubits in the system

Returns: A function that takes a quantum circuit and applies the Grover oracle Uf to it.

grover-algorithm clj

(grover-algorithm backend search-space-size oracle-fn)

(grover-algorithm backend search-space-size oracle-fn options)

Implement Grover's search algorithm.

Grover's algorithm provides a quadratic speedup for searching unsorted databases. For N items, classical search requires O(N) queries, while Grover's requires O(√N).

Algorithm steps:

1. Initialize uniform superposition |+⟩^⊗n
2. Repeat ~π√N/4 times: a. Apply oracle (marks target items) b. Apply diffusion operator (inversion about average)
3. Measure to find target item with high probability

Parameters:

• backend: Quantum backend implementing the QuantumBackend protocol
• search-space-size: Number of items to search through (must be power of 2)
• oracle-fn: Function that returns true for target items Takes basis state index as input
• options: Optional map with execution options (default: {:shots 1024})

Returns: Map containing:

• :result - Most likely measurement outcome
• :probability - Probability of measuring the target
• :iterations - Number of Grover iterations performed
• :circuit - The quantum circuit used
• :execution-result - Full backend execution result
• :target-indices - List of target state indices
• :measurement-statistics - Detailed measurement statistics

Example: (grover-algorithm backend 4 #(= % 2)) ; Search for item at index 2 in 4-item space

grover-circuit clj

(grover-circuit n-qubits oracle-fn)

(grover-circuit n-qubits oracle-fn iterations)

(grover-circuit n-qubits oracle-fn iterations options)

Build the complete quantum circuit for Grover's search algorithm.

Constructs a quantum circuit that implements Grover's algorithm, including:

1. Initial state preparation (uniform superposition)
2. Repeated Grover iterations (oracle + diffusion operator)
3. Optional final measurement

Parameters:

• n-qubits: Number of qubits (determines search space size 2^n)
• oracle-fn: Function that takes a basis state index and returns true for target states
• iterations: Number of Grover iterations (if not provided, uses optimal π√N/4)
• options: Optional map with keys:
  • :add-measurements? - Whether to add measurement operations (default: false)

Returns: Quantum circuit implementing Grover's algorithm

Example: (grover-circuit 3 #(= % 5)) ; Search for state |101⟩ in 3-qubit space (grover-circuit 2 #(contains? #{1 2} %) 1 {:add-measurements? true})

grover-diffusion-circuit clj

(grover-diffusion-circuit n-qubits)

Build the quantum circuit for Grover's diffusion operator.

The diffusion operator applies inversion about the average amplitude. It implements 2|ψ⟩⟨ψ| - I where |ψ⟩ is the uniform superposition state.

Algorithm:

1. Apply H gates to all qubits (transform to computational basis)
2. Apply X gates to all qubits (flip all bits)
3. Apply multi-controlled Z gate to flip phase of |11...1⟩
4. Apply X gates to all qubits again (flip back)
5. Apply H gates to all qubits again (transform back to superposition basis)

Parameters:

• n-qubits: Number of qubits in the system

Returns: A function that takes a quantum circuit and applies the diffusion operator.

multi-controlled-z clj

(multi-controlled-z circuit control-qubits target)

Apply a multi-controlled Z gate to flip the phase of |11...1⟩ state.

Uses the decomposition MCZ = H + MCX + H, where MCX is implemented using Toffoli gates and CNOT gates for multi-control scenarios.

Parameters:

• circuit: Quantum circuit to add the gate to
• control-qubits: Vector of control qubit indices
• target: Index of target qubit

Returns: Updated quantum circuit with multi-controlled Z gate

optimal-grover-iterations clj

(optimal-grover-iterations N M)

Calculate the optimal number of iterations for Grover's algorithm.

For N items with M marked items, optimal iterations ≈ π√(N/M)/4

Parameters:

• N: Total number of items in search space
• M: Number of marked (target) items

Returns: Optimal number of iterations (integer)