Grover / GroveFold — Technical Protocol & Benchmark Report

1. Executive summary

Grover search treats folding as unstructured search: build an oracle that flips the phase of any conformation whose energy is below a threshold E_th, then amplify those marked states with ⌊π/4·√(N/M)⌋ Grover iterations. Unlike VQE (which optimizes), Grover provably concentrates probability on the answer set and gives a quadratic speedup over classical enumeration.

• Answer states reproduce the paper exactly. Every classical validation case (SP s=2/3/6) matches the paper's answer-state tables.
• The quantum circuit concentrates as predicted. P(answer) reaches 97.9–100% at the optimal iteration count k_opt across SP, MR and MR-MP — amplifications up to 256× over the random baseline.
• GPU pays off here (unlike VQE) because Grover circuits are deep and wide (16–33 qubits): the heaviest run (MR-MP s=3, 24q) was 3.6× faster on GPU.

2. Problem encoding & the three models

Each residue's turn is one of several categories (Neg, Pos, H1, Pol1, Pol2). A chain of s turns is encoded in n = 3s data qubits; the search space is N = 2ⁿ. The oracle marks the M states whose energy ≤ E_th. The three models differ only in the energy function:

Answer states are reported as category strings, e.g. SP s=2 → ['Neg-Pos', 'Pos-Neg']; SP s=3 → ['Neg-Pos-Neg', 'Pos-Neg-Pos'] — these match Khatami Tables S1/S2/S3 exactly.

3. Grover search & k_opt

|ψ0> = H^n |0>                       # uniform superposition over N conformations
repeat k times:
    |ψ> = Oracle |ψ>                  # phase-flip states with energy <= E_th  (the M answers)
    |ψ> = Diffuser |ψ>                # inversion about the mean (amplitude amplification)
measure                              # collapses onto an answer with high probability

k_opt = floor( (pi/4) * sqrt(N / M) )                # SP: closed form
k_opt = argmax_K  sin^2( (2K+1) * arcsin(sqrt(M/N)) ) # MR: exact enumeration (k_opt_mr)
amplification = P(answer at k_opt) / (M / N)         # vs random baseline

Over- or under-shooting k_opt reduces P(answer) (amplitude over-rotates), so the sweep R = 0…2·k_opt+1 is run and the peak is confirmed to land at k_opt (peak_matches_kopt).

4. Oracle construction (Draper-QFT arithmetic, Fig 1B)

The oracle is a genuine gate-level arithmetic circuit, not a lookup. It computes each conformation's energy into an accumulator register, compares it to E_th, kicks back a phase if below threshold, then uncomputes:

1. ACCUMULATE   for each contact pair, add its (fixed-point) energy into an
                accumulator via Draper QFT addition  (QFT → phase rotations → IQFT)
2. COMPARE      compare accumulator to E_th (subtract, inspect sign qubit)
3. KICKBACK     phase-flip when energy <= E_th  (marks the answer states)
4. UNCOMPUTE    reverse steps 2–1 to restore work qubits (Bennett uncompute)

Implemented in grove_adapter._build_grover_circuit (SP) and oracle_mr.build_grover_mr(MR / MR-MP). MR uses uniform_distance_matrix for the distance weights and k_opt_mr for the exact optimal iteration count. Compact-accumulator design: the project reuses one accumulator register sequentially (high depth, few qubits) rather than the paper's unrolled parallel work qubits — see §10.

5. Code map

6. Reproduction environment (fusion4)

7. Exact reproduction commands

# SP — classical answer-state validation (all s, all E_th)
python run_grover_strict.py --validate

# SP — quantum sweep (single case), capped
python run_grover_strict.py --single --s 3 --i 2 --eth -7 --rmax 25 --device GPU --max-threads 85

# MR (p=5) and MR-MP (p=10)
python run_grover_mr.py --s 3 --device GPU --precision 5    # MR
python run_grover_mr.py --s 3 --device GPU --precision 10   # MR-MP

# MR circuit validation (qubit count vs Table 1)
python run_grover_mr.py --s 2 --validate

8. Benchmark results (fusion4)

8.1 Classical answer-state validation (vs paper Tables S1–S3)

8.2 SP quantum runs (Grover amplification)

8.3 MR / MR-MP quantum runs (distance-weighted)

Reading these: every quantum run peaks exactly at k_opt and reaches 97.9–100% P(answer) — the oracle marks the right states and amplitude amplification works as the theory predicts. Higher s (more turns) gives larger amplification because the search space N grows faster than the answer set M.

9. Resource utilization (time, CPU & memory)

Instrumented per run by a MemMonitor thread (psutil RSS), time.process_time() (CPU-seconds), and nvidia-smi memory.used. Unlike VQE, Grover circuits are deep and wide, so both time and memory grow sharply with qubit count.

Memory grows with qubits and precision: ~2 GB at 16q (MR s=2) up to ~12 GB at 24q (MR-MP s=3). CPU-time ≫ wall (e.g. 2.21M CPU-seconds for MR-MP s=3 on CPU → ~57 effective cores under the 85-thread cap). GPU wins decisively at depth: the 24-qubit MR-MP s=3 run was 10.8 h on CPU vs 3 h on GPU (3.6×) — the opposite of VQE's tiny circuits, where GPU was slower.

10. Known deviations & next steps

• Compact oracle vs paper Table 1 qubit counts. The project's MR oracle reuses one accumulator register sequentially, so s=2 MR uses 16 qubits (vs the paper's unrolled 151). Same physics, same answer states (verified vs Tables S2/S3) — a deliberate depth-for-qubit-count tradeoff, not a fidelity loss.
• SP s=6 i=5 — 33 qubits, MPS, partial probe. This case auto-runs on a matrix-product-state backend (statevector would be 2³³·16 B ≈ 137 GB). Its optimal iteration count is k_opt = 284 (N=262,144, M=2), so the --rmax 4 sweep is a deliberate feasibility probe (R=0–4), not the full amplification curve. It was first launched on CPU-MPS where the deep QFT-arithmetic oracle drives the MPS bond dimension up and a single oracle application is extremely slow (no iteration completed in ~45 h, output block-buffered). It is now re-running on GPU-MPS, unbuffered: R=0 returns in 0.3 s; each subsequent iteration applies the full 33-qubit oracle (the cost driver). The ≤26-qubit results in §8 are all complete and validated; the s=6 amplification peak at R≈284 is beyond practical exact-simulation reach.
• QFTGate shim is required on qiskit 1.1.1 (no native QFTGate); it maps to QFT(n).to_gate() and is behaviorally identical.
• IBM hardware runs were out of scope — all results are exact statevector / MPS simulation.
• Next: finish SP s=6 i=5 (or switch it to MPS to bound memory); add MR variants for s≥4 if a deeper distance-aware sweep is wanted.