Grover Search (GroveFold)
Find low-energy peptide shapes by quantum search — with a provable quadratic speedup over checking every shape one by one.
What is Grover search?
Imagine a phone book with a million entries and you want the one matching a number — classically you might check them one at a time. Grover's algorithm is a quantum trick that finds the right entries in roughly √(million) steps instead of a million. For folding, the "entries" are all possible 3D shapes of a peptide, and the ones we want are the low-energy (stable) shapes.
Where VQE optimizes toward a good shape, Grover searches for all shapes below an energy threshold and provably amplifies them until a measurement almost always returns one of the answers.
The oracle
A circuit that secretly “marks” every shape whose energy is below your threshold.
Amplification
Repeated Grover steps grow the marked shapes’ probability and shrink the rest.
Measure
After the optimal number of steps, a measurement returns a correct low-energy shape ~99% of the time.
How it works
Spread out over all shapes
Start in an equal superposition of every possible conformation at once.
Mark the good shapes
An arithmetic oracle computes each shape's energy and flips the phase of those below the threshold E_th.
Amplify
A "diffusion" step nudges probability toward the marked shapes. Each repeat makes them more likely.
Stop at the sweet spot
There's an optimal number of repeats, k_opt = ⌊π/4·√(N/M)⌋. Stop there — going further actually reduces the probability.
Measure
Measuring returns a low-energy conformation with very high probability (97–100% in our runs).
Three energy models
All three search the same way; they differ in how realistically energy is computed.
SP — Simplified Potential
Small integer energies, no distance dependence. Fast, ideal for validating that the search returns the right shapes.
MR — More Realistic
Energies weighted by how close residues actually are in space — physically meaningful folding.
MR-MP — More Realistic, More Precision
Same physics as MR with higher-precision arithmetic — the most faithful, and the most demanding to simulate.
Reading your results
| Metric | What it means | What good looks like |
|---|---|---|
| P(answer) | Chance a measurement lands on a correct low-energy shape. | 97–100% at the optimal step count. |
| Amplification | How much more likely the answer is than blind guessing. | Up to 256× in our runs. |
| k_opt | The optimal number of Grover repeats. | The probability peak should land exactly here. |
| Answer states | The actual shapes found (as turn categories). | Match the known reference shapes. |
EXAMPLE — 3-turn chain (s=3)
Out of 512 possible shapes, only 2 are correct. After 12 Grover steps, a measurement returns one of them 99.98% of the time — a 256× boost over random guessing. The two shapes found, Neg-Pos-Neg and Pos-Neg-Pos, are exactly the published answers.
When to use Grover (and its limits)
- Use it when you want all shapes below an energy cutoff, with a guaranteed high success probability.
- Pick the model by realism vs cost: SP to validate, MR for physical folding, MR-MP for the highest fidelity.
- Choose GPU for the big runs. Grover circuits are deep — GPU was up to 3.6× faster on the largest case (the opposite of VQE's tiny circuits).
- Mind the size. Beyond ~26 qubits the simulation switches to a memory-leaner method; very long chains become demanding.