Skip to content

GroverAlgorithm: extend to general oracle and multi-target search #23

@sotashimozono

Description

@sotashimozono

Current state

GroverAlgorithm.jl provides the basic circuit components for Grover's algorithm via ITensors/ITensorMPS. The Toffoli gate is implemented in example/toffoli.jl.

Missing functionality

  1. General oracle: the current implementation likely hard-codes a specific target state. A general oracle should accept any boolean predicate or a list of target bitstrings.

  2. Multi-target search: Grover's works for k targets with O(sqrt(N/k)) oracle calls — not currently tested.

  3. MPS simulation scaling: no benchmark comparing exact statevector vs MPS with varying chi to identify where entanglement buildup degrades accuracy.

  4. Quantum circuit diagram output: the QuantikzIO module generates LaTeX diagrams but there is no automated test that it produces valid Quantikz output.

Proposed tasks

  • Generalize oracle to accept target_states::Vector{String} (bitstring list)
  • Test multi-target Grover: 1 target in 4-qubit space → 1 Grover step; 2 targets → adjusted iterations
  • Benchmark MPS chi required to maintain |<found|target>|² > 0.99 for n=6–12 qubits
  • Add test/core/test_oracle.jl with at least 2 oracle variants
  • Validate Quantikz output compiles with pdflatex in a test

Metadata

Metadata

Assignees

No one assigned

    Labels

    feature新機能・既存アルゴリズムの拡張research研究・新規手法・未検証アイデア

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions