python/quantum/grover_sha520.py

"""
Grover's Algorithm for SHA-520 Preimage Search

Implements Grover oracle and amplitude amplification for quantum preimage attacks.
"""

import math
from typing import Dict, Any, List, Tuple, Optional

try:
    from .quantum_sha520 import ReversibleSHA520, QuantumCircuit
except ImportError:  # pragma: no cover - supports direct script execution
    from quantum_sha520 import ReversibleSHA520, QuantumCircuit


class GroverSHA520:
    """Grover's algorithm applied to SHA-520 preimage search.

    Uses reversible SHA-520 as oracle within Grover amplitude amplification.
    """

    def __init__(
        self,
        rounds: int = 80,
        target_hash: bytes = b'\x00' * 64,
        n_qubits_message: int = 64,
    ):
        """Initialize Grover SHA-520 solver.

        Parameters
        ----------
        rounds : int
            SHA-520 round count
        target_hash : bytes
            Target hash bytes
        n_qubits_message : int
            Qubits representing message space
        """
        self.rounds = rounds
        self.target_hash = target_hash
        self.n_qubits_message = n_qubits_message

        # Search space size
        self.search_space = 2 ** n_qubits_message

        # Reversible SHA-520 oracle
        self.rev_sha = ReversibleSHA520(rounds, n_qubits_message)

    def optimal_iterations(self) -> int:
        """Compute optimal number of Grover iterations.

        Returns
        -------
        int
            Number of iterations ≈ π/4 * √(search_space / solutions)

        Notes
        -----
        Assumes 1 solution (preimage of target hash).
        """
        # For 1 solution: iterations ≈ (π/4) * √N
        return int((math.pi / 4.0) * math.sqrt(self.search_space))

    def build_grover_preimage(self) -> QuantumCircuit:
        """Build complete Grover circuit for SHA-520 preimage search.

        Returns
        -------
        QuantumCircuit
            Full Grover algorithm circuit
        """
        total_qubits = self.rev_sha.total_qubits + 1  # +1 for ancilla phase qubit
        circuit = QuantumCircuit(total_qubits, "Grover_SHA520_Preimage")

        iterations = self.optimal_iterations()

        # Initialize superposition (message qubits)
        for i in range(self.n_qubits_message):
            circuit.h(i)

        # Initialize phase ancilla
        circuit.x(total_qubits - 1)
        circuit.h(total_qubits - 1)

        # Amplitude amplification loop
        for iteration in range(iterations):
            # Oracle: mark target hash
            self._apply_oracle(circuit)

            # Diffusion operator
            self._apply_diffusion(circuit)

        # Measurement
        message_bits = list(range(self.n_qubits_message))
        classical_bits = list(range(self.n_qubits_message))
        circuit.measure(message_bits, classical_bits)

        return circuit

    def _apply_oracle(self, circuit: QuantumCircuit) -> None:
        """Apply SHA-520 oracle.

        The oracle applies a phase flip to states that hash to target_hash.

        Parameters
        ----------
        circuit : QuantumCircuit
            Circuit to add oracle to
        """
        oracle = self.rev_sha.build_oracle(self.target_hash)

        # Append oracle gates to main circuit
        for gate in oracle.gates:
            circuit.gates.append(gate)

    def _apply_diffusion(self, circuit: QuantumCircuit) -> None:
        """Apply Grover diffusion operator.

        D = 2|s⟩⟨s| - I, where |s⟩ is the uniform superposition.

        This amplifies amplitude of marked states.

        Parameters
        ----------
        circuit : QuantumCircuit
            Circuit to add diffusion to
        """
        # H on all message qubits
        for i in range(self.n_qubits_message):
            circuit.h(i)

        # X on all message qubits
        for i in range(self.n_qubits_message):
            circuit.x(i)

        # Multi-controlled Z (if all qubits are 0, apply phase)
        # This is the inversion about average operation
        self._multi_controlled_z(circuit, list(range(self.n_qubits_message)))

        # X on all message qubits (uncompute)
        for i in range(self.n_qubits_message):
            circuit.x(i)

        # H on all message qubits (uncompute)
        for i in range(self.n_qubits_message):
            circuit.h(i)

    def _multi_controlled_z(self, circuit: QuantumCircuit, control_qubits: List[int]) -> None:
        """Apply multi-controlled Z gate.

        Applies Z to last qubit when all controls are 1.

        Parameters
        ----------
        circuit : QuantumCircuit
            Circuit
        control_qubits : list
            Control qubits
        """
        # For small numbers of controls, decompose into Toffoli + single qubit gates
        n_controls = len(control_qubits)

        if n_controls == 0:
            circuit.rz(0, math.pi)
        elif n_controls == 1:
            circuit.rz(control_qubits[0], math.pi)
        elif n_controls == 2:
            c1, target = control_qubits[:2]
            circuit.h(target)
            circuit.cx(c1, target)
            circuit.h(target)
        else:
            circuit.gates.append({"type": "MCZ", "qubits": list(control_qubits)})

    def estimate_resources(self) -> Dict[str, Any]:
        """Estimate circuit resources for Grover attack.

        Returns
        -------
        dict
            Resource metrics
        """
        iterations = self.optimal_iterations()
        oracle_resources = self.rev_sha.resource_estimate()

        # Diffusion depth ≈ 4 * H-layers + MCZ
        diffusion_depth = 40 + (2 ** self.n_qubits_message)

        total_depth = iterations * (oracle_resources["estimated_depth"] + diffusion_depth)

        return {
            "target_bits": self.n_qubits_message,
            "search_space": self.search_space,
            "grover_iterations": iterations,
            "oracle_depth": oracle_resources["estimated_depth"],
            "diffusion_depth": diffusion_depth,
            "total_circuit_depth": total_depth,
            "total_qubits": oracle_resources["total_qubits"] + 1,
            "estimated_gates": iterations * (oracle_resources["estimated_gates"] + 100),
        }


def optimal_iterations(search_space: int, solutions: int = 1) -> int:
    """Compute optimal Grover iterations for given search space.

    Parameters
    ----------
    search_space : int
        Total size of search space (2^n)
    solutions : int
        Number of solutions (marked states)

    Returns
    -------
    int
        Number of amplitude amplification iterations

    Notes
    -----
    Formula: iterations = π/4 * √(N/M)
    where N = search_space, M = solutions
    """
    if solutions >= search_space:
        return 1

    return max(1, int((math.pi / 4.0) * math.sqrt(search_space / solutions)))


def estimate_resources(
    rounds: int,
    target_bits: int,
    solutions: int = 1,
) -> Dict[str, Any]:
    """Estimate Grover resources for SHA-520 variant.

    Parameters
    ----------
    rounds : int
        SHA-520 round count
    target_bits : int
        Number of bits in search space
    solutions : int
        Number of solutions (typically 1 for preimage)

    Returns
    -------
    dict
        Resource estimates for Grover attack
    """
    search_space = 2 ** target_bits
    iterations = optimal_iterations(search_space, solutions)

    # Oracle depth scales with rounds and target bits
    # Rough estimate: 100 + 2*rounds gates for oracle
    oracle_depth = 100 + 2 * rounds

    # Diffusion: ~40 + 2^n for multi-controlled Z
    diffusion_depth = 40 + max(20, 2 ** min(target_bits, 10))

    # Total depth = iterations * (oracle + diffusion)
    total_depth = iterations * (oracle_depth + diffusion_depth)

    # Qubits needed
    data_qubits = target_bits
    ancilla_qubits = max(100, 3 * target_bits + rounds)
    total_qubits = data_qubits + ancilla_qubits

    return {
        "rounds": rounds,
        "target_bits": target_bits,
        "search_space": search_space,
        "solutions": solutions,
        "grover_iterations": iterations,
        "oracle_depth": oracle_depth,
        "diffusion_depth": diffusion_depth,
        "total_circuit_depth": total_depth,
        "data_qubits": data_qubits,
        "ancilla_qubits": ancilla_qubits,
        "total_logical_qubits": total_qubits,
        "estimated_total_gates": iterations * (oracle_depth + diffusion_depth),
    }


def grover_speedup_vs_classical(
    target_bits: int,
    rounds: int = 80,
    gate_time_us: float = 100.0,
) -> Dict[str, Any]:
    """Compare Grover quantum attack to classical preimage search.

    Parameters
    ----------
    target_bits : int
        Bits of hash output being targeted
    rounds : int
        SHA-520 round count
    gate_time_us : float
        Quantum gate time in microseconds

    Returns
    -------
    dict
        Speedup factors and absolute times
    """
    # Grover iterations
    search_space = 2 ** target_bits
    iterations = optimal_iterations(search_space, 1)

    # Circuit depth
    resources = estimate_resources(rounds, target_bits)
    circuit_depth = resources["total_circuit_depth"]

    # Grover time estimate (in seconds)
    grover_time_sec = (circuit_depth * gate_time_us) * 1e-6

    # Classical preimage: 2^target_bits hash evaluations
    # Assume 1 μs per hash (SHA-520 is slow, but this is conservative)
    classical_time_sec = search_space * 1e-6

    # Speedup
    speedup = classical_time_sec / max(grover_time_sec, 1e-9)

    return {
        "target_bits": target_bits,
        "rounds": rounds,
        "search_space": search_space,
        "grover_iterations": iterations,
        "circuit_depth": circuit_depth,
        "gate_time_us": gate_time_us,
        "grover_time_sec": grover_time_sec,
        "classical_time_sec": classical_time_sec,
        "speedup_factor": speedup,
        "classical_advantage": classical_time_sec < grover_time_sec,
    }


if __name__ == "__main__":
    print("Grover's Algorithm for SHA-520 Preimage Search")
    print("=" * 60)

    # Test 4-round SHA-520 with 32-bit target
    grover = GroverSHA520(rounds=4, target_hash=b'\x00' * 64, n_qubits_message=32)

    print(f"\n4-round SHA-520, 32-bit search space:")
    print(f"  Search space: 2^32 = {grover.search_space:,}")
    print(f"  Optimal iterations: {grover.optimal_iterations()}")

    resources = grover.estimate_resources()
    print(f"  Circuit depth: {resources['total_circuit_depth']}")
    print(f"  Total qubits: {resources['total_qubits']}")
    print(f"  Estimated gates: {resources['estimated_gates']}")

    # Build circuit
    circuit = grover.build_grover_preimage()
    print(f"\n  Circuit: {circuit}")

    # Speedup comparison
    print("\n" + "=" * 60)
    print("Quantum vs Classical Speedup:")

    for bits in [16, 32, 48, 64]:
        speedup = grover_speedup_vs_classical(bits, rounds=80)
        print(
            f"\n{bits}-bit target:"
            f"\n  Grover time: {speedup['grover_time_sec']:.2e} sec"
            f"\n  Classical time: {speedup['classical_time_sec']:.2e} sec"
            f"\n  Speedup: {speedup['speedup_factor']:.2e}x"
        )