atlas_q.grover

Grover’s Search Algorithm for Quantum Database Search

Implements Grover’s amplitude amplification algorithm for searching unstructured databases with quadratic speedup over classical methods.

Mathematical Background: - Search space: N = 2^n elements - Marked items: M items to find - Classical complexity: O(N) - Quantum complexity: O(√(N/M)) iterations - Optimal iterations: k* = π/4 * √(N/M)

Features: - Oracle construction for various marking patterns - Amplitude amplification with diffusion operator - Automatic optimal iteration calculation - Integration with AdaptiveMPS for scalability - Support for multiple marked items - Flexible oracle types (function-based, bitmap, structured)

Author: ATLAS-Q Contributors Date: November 2025 License: MIT

class atlas_q.grover.GroverConfig(n_qubits, oracle_type='function', auto_iterations=True, max_iterations=1000, chi_max=256, device='cuda', dtype=torch.complex128, verbose=False, measure_success_prob=False)

Bases: object

Configuration for Grover’s algorithm

Attributes:

n_qubits: Number of qubits (search space size = 2^n_qubits) oracle_type: Type of oracle (‘function’, ‘bitmap’, ‘structured’) auto_iterations: Automatically calculate optimal iterations max_iterations: Maximum iterations (safety limit) chi_max: Maximum bond dimension for MPS device: ‘cuda’ or ‘cpu’ dtype: torch.complex64 or torch.complex128 verbose: Print progress information measure_success_prob: Track success probability after each iteration

n_qubits: int

oracle_type: str = 'function'

auto_iterations: bool = True

max_iterations: int = 1000

chi_max: int = 256

device: str = 'cuda'

dtype: dtype = torch.complex128

verbose: bool = False

measure_success_prob: bool = False

class atlas_q.grover.OracleBase(n_qubits, device='cuda', dtype=torch.complex128)

Bases: object

Base class for quantum oracles

Methods

apply(mps)	Apply oracle to MPS (marks all target states)
get_marked_count()	Return number of marked items
mark(mps, state)	Mark a specific basis state by flipping its phase

mark(mps, state)

Mark a specific basis state by flipping its phase

apply(mps)

Apply oracle to MPS (marks all target states)

Returns:

New MPS after oracle application

get_marked_count()

Return number of marked items

class atlas_q.grover.FunctionOracle(n_qubits, marking_fn, device='cuda', dtype=torch.complex128)

Bases: OracleBase

Oracle based on a marking function

Marks states where f(x) = True by applying phase flip. Implements O_f |x⟩ = (-1)^f(x) |x⟩

Example:

# Mark state |5⟩ oracle = FunctionOracle(n_qubits=4, marking_fn=lambda x: x == 5)

Methods

apply(mps)	Apply oracle by marking all states where marking_fn returns True
get_marked_count()	Return number of marked items
mark(mps, state)	Mark a specific basis state by flipping its phase

apply(mps)

Apply oracle by marking all states where marking_fn returns True

Returns:

New MPS after oracle application

class atlas_q.grover.BitmapOracle(n_qubits, marked_states, device='cuda', dtype=torch.complex128)

Bases: OracleBase

Oracle based on explicit bitmap of marked states

More efficient than FunctionOracle for small marked sets.

Example:

oracle = BitmapOracle(n_qubits=4, marked_states={3, 7, 11})

Methods

apply(mps)	Apply oracle by marking all states in bitmap
get_marked_count()	Return number of marked items
mark(mps, state)	Mark a specific basis state by flipping its phase

apply(mps)

Apply oracle by marking all states in bitmap

Returns:

New MPS after oracle application

class atlas_q.grover.DiffusionOperator(n_qubits, device='cuda', dtype=torch.complex128)

Bases: object

Grover diffusion operator (inversion about average)

Implements: D = 2|ψ⟩⟨ψ| - I where |ψ⟩ = |+⟩^⊗n

Mathematical form:

D = H^⊗n (2|0⟩⟨0| - I) H^⊗n

This reflects amplitudes about their average, amplifying marked states.

Methods

apply(mps)

Apply diffusion operator: 2|+⟩⟨+| - I

apply(mps)

Apply diffusion operator: 2|+⟩⟨+| - I

Decomposition: 1. H^⊗n (transform to computational basis) 2. 2|0⟩⟨0| - I (conditional phase shift using MPO) 3. H^⊗n (transform back)

Returns:

New MPS after diffusion

class atlas_q.grover.GroverSearch(oracle, config)

Bases: object

Grover’s Search Algorithm Implementation

Performs quantum search on an unstructured database with O(√N) queries.

Algorithm:

1. Initialize to |+⟩^⊗n (uniform superposition)

2. Repeat k times:

   1. Apply oracle O (mark target states)

   2. Apply diffusion operator D (amplify marked states)

3. Measure to find marked item with high probability

Example:

>>> config = GroverConfig(n_qubits=4)
>>> oracle = FunctionOracle(4, lambda x: x == 7)
>>> grover = GroverSearch(oracle, config)
>>> result = grover.run()
>>> print(f"Found item: {result['measured_state']}")
Found item: 7

Methods

plot_convergence([save_path])	Plot success probability vs iteration
run([iterations])	Run Grover's algorithm

run(iterations=None)

Run Grover’s algorithm

Args:

iterations: Number of iterations (None = auto-calculate optimal)

Returns:

Dictionary with results:

• measured_state: Most likely measurement outcome

• success_probability: Probability of measuring marked item

• iterations_used: Number of iterations performed

• runtime_ms: Execution time in milliseconds

• bond_dims: Final MPS bond dimensions

plot_convergence(save_path=None)

Plot success probability vs iteration

Args:

save_path: Optional path to save figure

atlas_q.grover.grover_search(n_qubits, marked_states, iterations=None, device='cuda', verbose=False)

Convenience function to run Grover’s search

Args:

n_qubits: Number of qubits marked_states: Either set/list of marked states or marking function iterations: Number of iterations (None = auto) device: ‘cuda’ or ‘cpu’ verbose: Print progress

Returns:

Results dictionary

Example:

>>> result = grover_search(4, marked_states={7}, verbose=True)
>>> print(f"Found: {result['measured_state']}")
Found: 7

atlas_q.grover.calculate_grover_iterations(n_qubits, n_marked)

Calculate optimal number of Grover iterations

Args:

n_qubits: Number of qubits n_marked: Number of marked items

Returns:

Optimal iteration count

Overview

The grover module implements Grover’s quantum search algorithm for unstructured database search with quadratic speedup. This algorithm finds marked items in a search space of size \(N\) using \(O(\sqrt{N})\) queries, compared to \(O(N)\) classically.

The implementation integrates with ATLAS-Q’s Matrix Product State (MPS) backend for scalable simulation of larger systems.

Mathematical Background

Grover’s algorithm searches for marked items in an unstructured database using amplitude amplification:

1. Initialize to uniform superposition \(|s\rangle = H^{\otimes n}|0\rangle^{\otimes n}\)

2. Repeat \(k^* = \lfloor\frac{\pi}{4}\sqrt{N/M}\rfloor\) times:

   1. Apply oracle \(O_f|x\rangle = (-1)^{f(x)}|x\rangle\) (marks target states)

   2. Apply diffusion operator \(D = 2|s\rangle\langle s| - I\) (amplifies marked states)

3. Measure to find marked item with high probability (\(\gtrsim 95\%\))

Where:

• \(N = 2^n\) is the search space size

• \(M\) is the number of marked items

• \(k^*\) is the optimal number of iterations

Classes

GroverSearch	Grover's Search Algorithm Implementation
GroverConfig	Configuration for Grover's algorithm
OracleBase	Base class for quantum oracles
FunctionOracle	Oracle based on a marking function
BitmapOracle	Oracle based on explicit bitmap of marked states
DiffusionOperator	Grover diffusion operator (inversion about average)

Functions

grover_search	Convenience function to run Grover's search
calculate_grover_iterations	Calculate optimal number of Grover iterations

GroverSearch

class atlas_q.grover.GroverSearch(oracle, config)

Bases: object

Grover’s Search Algorithm Implementation

Performs quantum search on an unstructured database with O(√N) queries.

Algorithm:

1. Initialize to |+⟩^⊗n (uniform superposition)

2. Repeat k times:

   1. Apply oracle O (mark target states)

   2. Apply diffusion operator D (amplify marked states)

3. Measure to find marked item with high probability

Example:

>>> config = GroverConfig(n_qubits=4)
>>> oracle = FunctionOracle(4, lambda x: x == 7)
>>> grover = GroverSearch(oracle, config)
>>> result = grover.run()
>>> print(f"Found item: {result['measured_state']}")
Found item: 7

Methods

plot_convergence([save_path])	Plot success probability vs iteration
run([iterations])	Run Grover's algorithm

Main implementation of Grover’s quantum search algorithm.

The algorithm amplifies the probability amplitude of marked states through repeated application of the oracle and diffusion operators.

Constructor

grover = GroverSearch(oracle, config)

Parameters:

• oracle (OracleBase): Oracle that marks target states

• config (GroverConfig): Algorithm configuration

Methods

__init__(oracle, config)
run([iterations])	Run Grover's algorithm
plot_convergence([save_path])	Plot success probability vs iteration

Example

from atlas_q.grover import GroverSearch, GroverConfig, BitmapOracle

# Configure algorithm
config = GroverConfig(n_qubits=4, device='cpu')

# Create oracle marking state 7
oracle = BitmapOracle(4, {7}, device='cpu')

# Run search
grover = GroverSearch(oracle, config)
result = grover.run()

print(f"Found state: {result['measured_state']}")
print(f"Success probability: {result['success_probability']:.3f}")

run(iterations=None)

Run Grover’s algorithm

Args:

iterations: Number of iterations (None = auto-calculate optimal)

Returns:

Dictionary with results:

• measured_state: Most likely measurement outcome

• success_probability: Probability of measuring marked item

• iterations_used: Number of iterations performed

• runtime_ms: Execution time in milliseconds

• bond_dims: Final MPS bond dimensions

plot_convergence(save_path=None)

Plot success probability vs iteration

Args:

save_path: Optional path to save figure

GroverConfig

class atlas_q.grover.GroverConfig(n_qubits, oracle_type='function', auto_iterations=True, max_iterations=1000, chi_max=256, device='cuda', dtype=torch.complex128, verbose=False, measure_success_prob=False)

Bases: object

Configuration for Grover’s algorithm

Attributes:

n_qubits: Number of qubits (search space size = 2^n_qubits) oracle_type: Type of oracle (‘function’, ‘bitmap’, ‘structured’) auto_iterations: Automatically calculate optimal iterations max_iterations: Maximum iterations (safety limit) chi_max: Maximum bond dimension for MPS device: ‘cuda’ or ‘cpu’ dtype: torch.complex64 or torch.complex128 verbose: Print progress information measure_success_prob: Track success probability after each iteration

Configuration for Grover’s algorithm.

n_qubits

Number of qubits (search space size = \(2^{\\text{n_qubits}}\)).

oracle_type

Oracle type: 'function' or 'bitmap' (default: 'function').

auto_iterations

Automatically calculate optimal iterations (default: True).

max_iterations

Maximum iterations safety limit (default: 1000).

chi_max

Maximum MPS bond dimension (default: 256).

device

Compute device: 'cuda' or 'cpu' (default: 'cuda').

dtype

Data type: torch.complex64 or torch.complex128 (default: torch.complex128).

verbose

Print progress information (default: False).

measure_success_prob

Track success probability per iteration (default: False).

n_qubits: int

oracle_type: str = 'function'

auto_iterations: bool = True

max_iterations: int = 1000

chi_max: int = 256

device: str = 'cuda'

dtype: dtype = torch.complex128

verbose: bool = False

measure_success_prob: bool = False

OracleBase

class atlas_q.grover.OracleBase(n_qubits, device='cuda', dtype=torch.complex128)

Bases: object

Base class for quantum oracles

Methods

apply(mps)	Apply oracle to MPS (marks all target states)
get_marked_count()	Return number of marked items
mark(mps, state)	Mark a specific basis state by flipping its phase

Abstract base class for quantum oracles.

Oracles mark target states by applying a phase flip:

\[O_f|x\rangle = (-1)^{f(x)}|x\rangle\]

Methods

apply(mps)	Apply oracle to MPS (marks all target states)
get_marked_count()	Return number of marked items

mark(mps, state)

Mark a specific basis state by flipping its phase

apply(mps)

Apply oracle to MPS (marks all target states)

Returns:

New MPS after oracle application

get_marked_count()

Return number of marked items

FunctionOracle

class atlas_q.grover.FunctionOracle(n_qubits, marking_fn, device='cuda', dtype=torch.complex128)

Bases: OracleBase

Oracle based on a marking function

Marks states where f(x) = True by applying phase flip. Implements O_f |x⟩ = (-1)^f(x) |x⟩

Example:

# Mark state |5⟩ oracle = FunctionOracle(n_qubits=4, marking_fn=lambda x: x == 5)

Methods

apply(mps)	Apply oracle by marking all states where marking_fn returns True
get_marked_count()	Return number of marked items
mark(mps, state)	Mark a specific basis state by flipping its phase

Oracle based on a marking function \(f: \\{0,1\\}^n \\to \\{0,1\\}\).

Marks states where marking_fn(x) returns True.

Constructor

oracle = FunctionOracle(n_qubits, marking_fn, device='cpu')

Parameters:

• n_qubits (int): Number of qubits

• marking_fn (callable): Function that returns True for marked states

• device (str): Compute device

• dtype (torch.dtype): Data type

Example

from atlas_q.grover import FunctionOracle

# Mark even numbers
oracle = FunctionOracle(
    n_qubits=4,
    marking_fn=lambda x: x % 2 == 0,
    device='cpu'
)

# Mark powers of two
is_power_of_two = lambda x: x > 0 and (x & (x - 1)) == 0
oracle = FunctionOracle(4, is_power_of_two)

apply(mps)

Apply oracle by marking all states where marking_fn returns True

Returns:

New MPS after oracle application

BitmapOracle

class atlas_q.grover.BitmapOracle(n_qubits, marked_states, device='cuda', dtype=torch.complex128)

Bases: OracleBase

Oracle based on explicit bitmap of marked states

More efficient than FunctionOracle for small marked sets.

Example:

oracle = BitmapOracle(n_qubits=4, marked_states={3, 7, 11})

Methods

apply(mps)	Apply oracle by marking all states in bitmap
get_marked_count()	Return number of marked items
mark(mps, state)	Mark a specific basis state by flipping its phase

Oracle based on explicit bitmap of marked states.

More efficient than FunctionOracle for small marked sets.

Constructor

oracle = BitmapOracle(n_qubits, marked_states, device='cpu')

Parameters:

• n_qubits (int): Number of qubits

• marked_states (Set[int]): Set of marked state indices

• device (str): Compute device

• dtype (torch.dtype): Data type

Example

from atlas_q.grover import BitmapOracle

# Mark states 3, 7, and 11
oracle = BitmapOracle(
    n_qubits=4,
    marked_states={3, 7, 11},
    device='cpu'
)

apply(mps)

Apply oracle by marking all states in bitmap

Returns:

New MPS after oracle application

DiffusionOperator

class atlas_q.grover.DiffusionOperator(n_qubits, device='cuda', dtype=torch.complex128)

Bases: object

Grover diffusion operator (inversion about average)

Implements: D = 2|ψ⟩⟨ψ| - I where |ψ⟩ = |+⟩^⊗n

Mathematical form:

D = H^⊗n (2|0⟩⟨0| - I) H^⊗n

This reflects amplitudes about their average, amplifying marked states.

Methods

apply(mps)

Apply diffusion operator: 2|+⟩⟨+| - I

Grover diffusion operator (inversion about average).

Implements \(D = 2|s\rangle\langle s| - I\) where \(|s\rangle = H^{\otimes n}|0\rangle^{\otimes n}\).

Mathematical form:

\[D = H^{\otimes n}(2|0\rangle\langle 0| - I)H^{\otimes n}\]

This reflects amplitudes about their average, amplifying marked states.

apply(mps)

Apply diffusion operator: 2|+⟩⟨+| - I

Decomposition: 1. H^⊗n (transform to computational basis) 2. 2|0⟩⟨0| - I (conditional phase shift using MPO) 3. H^⊗n (transform back)

Returns:

New MPS after diffusion

Convenience Functions

grover_search

atlas_q.grover.grover_search(n_qubits, marked_states, iterations=None, device='cuda', verbose=False)

Convenience function to run Grover’s search

Args:

n_qubits: Number of qubits marked_states: Either set/list of marked states or marking function iterations: Number of iterations (None = auto) device: ‘cuda’ or ‘cpu’ verbose: Print progress

Returns:

Results dictionary

Example:

>>> result = grover_search(4, marked_states={7}, verbose=True)
>>> print(f"Found: {result['measured_state']}")
Found: 7

Convenience function for quick Grover searches.

Parameters:

• n_qubits (int): Number of qubits

• marked_states (Set[int], List[int], or callable): Marked states or marking function

• iterations (Optional[int]): Number of iterations (None = auto)

• device (str): 'cuda' or 'cpu' (default: 'cuda')

• verbose (bool): Print progress (default: False)

Returns:

Dictionary with search results

Example

from atlas_q.grover import grover_search

# Search for state 7 in 4-qubit space
result = grover_search(n_qubits=4, marked_states={7}, device='cpu')
print(f"Found: {result['measured_state']}")

# Search using function
result = grover_search(
    n_qubits=5,
    marked_states=lambda x: x % 3 == 0,  # Multiples of 3
    device='cpu'
)

calculate_grover_iterations

atlas_q.grover.calculate_grover_iterations(n_qubits, n_marked)

Calculate optimal number of Grover iterations

Args:

n_qubits: Number of qubits n_marked: Number of marked items

Returns:

Optimal iteration count

Calculate optimal number of Grover iterations.

Formula: \(k^* = \lfloor\frac{\pi}{4}\sqrt{N/M}\rfloor\)

Parameters:

• n_qubits (int): Number of qubits

• n_marked (int): Number of marked items

Returns:

Optimal iteration count (int)

Example

from atlas_q.grover import calculate_grover_iterations

# For N=16, M=1
k = calculate_grover_iterations(n_qubits=4, n_marked=1)
print(f"Optimal iterations: {k}")  # Output: 3

# For N=1024, M=4
k = calculate_grover_iterations(n_qubits=10, n_marked=4)
print(f"Optimal iterations: {k}")  # Output: 12

Performance Considerations

Scaling:

• Classical complexity: \(O(N)\) where \(N = 2^n\)

• Quantum complexity: \(O(\sqrt{N/M})\) iterations

• Each iteration: \(O(n \cdot \chi^2)\) where \(\chi\) is bond dimension

Bond Dimension:

Higher chi_max improves accuracy but increases computation time. Recommended values:

• Small systems (≤5 qubits): chi_max=32

• Medium systems (6-8 qubits): chi_max=64-128

• Large systems (≥9 qubits): chi_max=256-512

Device Selection:

• CPU: Better for small systems (≤6 qubits) or debugging

• CUDA: Significantly faster for larger systems (≥7 qubits)

Oracle Choice:

• BitmapOracle: Best for small explicit marked sets

• FunctionOracle: Best for pattern-based marking (e.g., “all even numbers”)

Implementation Details

MPO-Based Oracles:

The oracle implementation uses exact Matrix Product Operators (MPOs) to represent phase-flip operators. This provides:

• Exact oracle implementation (no approximations)

• Bond dimension 2 for single-state oracles

• Efficient contraction with MPS via apply_mpo_to_mps

• 94-100% success probability matching theoretical predictions

MPS Representation:

The quantum state is represented using Matrix Product States with controlled entanglement:

• Accuracy controlled by chi_max bond dimension parameter

• Recommended: chi_max=64-128 for 4-6 qubits, chi_max=256 for 7-8 qubits

• Higher chi_max improves accuracy at cost of performance

• For critical applications, run multiple searches and take majority vote

Performance Characteristics:

• 2-4 qubit systems: ~10-15 ms/iteration (CPU)

• 5-7 qubit systems: ~20-25 ms/iteration (CPU)

• GPU acceleration available for larger systems (≥7 qubits)

Best Practices

Optimal Iteration Count

For N items with M solutions, optimal iterations ≈ π/4 × √(N/M):

• Single solution: ~0.785√N iterations

• Monitor success probability to avoid over-rotation

• Can empirically tune by testing different iteration counts

Oracle Design

• Keep oracle simple (few gates) to minimize circuit depth

• Use phase kickback for efficient implementation

• Test oracle independently before full Grover circuit

Performance Optimization

1. Use χ=16-32 for up to 10 qubits (sufficient for Grover)

2. Enable GPU for n ≥ 8 qubits

3. Batch multiple searches if testing different oracles

4. Use stabilizer backend for Clifford-only oracles (faster)

Use Cases

Educational Applications

• Teaching quantum algorithms and amplitude amplification

• Demonstrating quantum speedup vs. classical search

• Understanding oracle-based quantum algorithms

Research Applications

• Benchmarking quantum simulators

• Studying entanglement in search algorithms

• Developing improved search variants

• Testing new oracle implementations

Practical Considerations

• For small N (< 100): Classical search faster

• For large N: Physical quantum computers needed for advantage

• Simulator useful for: algorithm development, education, benchmarking

See Also

• atlas_q.adaptive_mps - MPS backend used by Grover’s algorithm

• atlas_q.vqe_qaoa - Other variational quantum algorithms

• atlas_q.quantum_hybrid_system - Period-finding and Shor’s algorithm

• atlas_q.stabilizer_backend - Clifford circuit simulator

• Beginner’s Tutorial - Grover algorithm tutorial

References

[Grover96]

L. K. Grover, “A fast quantum mechanical algorithm for database search,” Proceedings of the 28th Annual ACM Symposium on Theory of Computing (1996). https://arxiv.org/abs/quant-ph/9605043

[Nielsen00]

M. A. Nielsen and I. L. Chuang, “Quantum Computation and Quantum Information,” Cambridge University Press (2000), Section 6.1.

[Brassard02]

G. Brassard, P. Høyer, M. Mosca, and A. Tapp, “Quantum Amplitude Amplification and Estimation,” Contemporary Mathematics, 305:53-74 (2002). https://arxiv.org/abs/quant-ph/0005055