Q047 · Mark / reflect / stop

Grover Amplitude Amplification

Can one extra round make the answer harder to find? Past the optimal number of rounds, yes. Each oracle call plus reflection turns the state a fixed step toward the targets. Once it gets there, another round turns it beyond them and the chance of success falls, so knowing when to stop matters.

Pick a small search space, mark the target entries and step through the rounds. Follow the phase oracle and the reflection as probability flows toward the targets and then back out again. Sample the readout and use the measured success rates to choose when to stop.

Ideal marked probability before readout $\text{—}$

Circuit oracle calls per trial $\text{—}$

Make a prediction

Will more oracle calls always make the target more likely?

Orange tiles are the marked targets. Drag the round selector, acquire a round scan and use the measured success rates to choose when to stop.

Try the contrasting cases, then test your prediction with recorded data.

Inspect an operation; acquisition always runs the complete circuit

Replay shows the model and adds no events.

Change one condition at a time

Compare the cases

Oracle–reflection rounds

k

3

Search qubits

n

4

Marked entries

M

1

Drag the round selector or use its slider. Changing rounds retains the scan; changing the oracle starts a new record.

Errors, resources and sampling

First marked index; targets wrap

j_0

0

Oracle phase offset

\epsilon_O

0^{\circ}

Reflection phase offset

\epsilon_D

0^{\circ}

Readout flip probability per bit

p_{\mathrm{read}}

0.000

Trials per setting

N_{\mathrm{shots}}

400

Random seed

s

1996

The Lab simulates the full complex state vector for four to sixty-four entries. The marked set is built into a teaching oracle; nothing is looked up in a real database. Phase offsets in the oracle and the reflection are coherent errors, and classical bit flips act on the final readout. Queries made by the circuit are counted separately from the one extra query that checks each result against the targets. The cost of building the oracle and of real hardware is not included.

Evidence and query counts

Simulated measurement record

Find the stopping point

Acquire a record to begin.

Colored bars and points come from records; thin gray marks are the model with the configured errors. Whiskers are pointwise 95% Wilson intervals for output or success fractions. They are not phase confidence intervals, simultaneous bands or guarantees after optional stopping.

Recorded success, 95% Wilson range

\text{—}

Round with the highest observed success among those sampled

\text{—}

All circuit / verification queries

\text{—}

The best observed round is a descriptive choice from this finite scan, not a certified optimum. Every output is checked against the known teaching oracle; that adds one verification query. No real-data oracle construction or hardware advantage is demonstrated.

Recomputed from the exported trials
Rounds	Trials	Successes	Circuit / verification queries

Latest 12 trials; CSV retains all trials
Trial	Setting	Reported bits	Integer	Circuit queries

Start with the essentials

Focus question: Which of the tested rounds gave the highest measured success, and how many queries did the scan use?
One-sentence intuition: The oracle by itself does not change any probability; interference in the reflection does. Together the two steps keep rotating the ideal state, so when you stop matters.

Core mathematical model

Uniform preparation

|s\rangle=\frac{1}{\sqrt N}\sum_{x=0}^{N-1}|x\rangle,\quad N=2^n

The targets are consecutive entries starting at the selected index, wrapping around at the end. The simulator knows them in advance.

Phase oracle

O_{\epsilon_O}|x\rangle=\begin{cases}e^{i(\pi+\epsilon_O)}|x\rangle&x\in\mathcal M\\|x\rangle&x\notin\mathcal M\end{cases}

You enter the phase offset in degrees, and it is converted to radians. This coherent error is different from a random bit flip.

Reflection with phase error

D_{\epsilon_D}=-I+\bigl(1-e^{i(\pi+\epsilon_D)}\bigr)|s\rangle\langle s|

The overall minus sign in front makes the error-free operator the usual inversion about the mean. With an error, the operator is still unitary.

The complete circuit

|\psi_k\rangle=(D_{\epsilon_D}O_{\epsilon_O})^k|s\rangle

Every complex amplitude is updated step by step. You can view the state right after any oracle or reflection step.

Ideal rotation formula

P_{\mathcal M}(k)=\sin^2((2k+1)\alpha),\quad\sin^2\alpha=M/N

This rotation formula holds for ideal phases, before any readout error. It serves as an independent check; the state vector is not computed from it.

Measured success and circuit cost

\widehat P_{\mathcal M}(k)=N_{\mathrm{success},k}/N_{\mathrm{shots},k},\quad C_O=kN_{\mathrm{shots},k}

Each reported output is also checked once against the target set. That extra query is counted separately as a verification query.

Common difficulties

The oracle is given the targets

Typical misconceptionThe simulator discovers a secret in a real database.

Better mental modelThe target set is handed to the teaching oracle in advance. Building a real oracle can be expensive, and this model leaves that cost out.

A negative amplitude is not a negative chance

Typical misconceptionAn arrow pointing the negative way means a negative chance.

Better mental modelThe arrow's direction is the complex phase and its length is the size of the amplitude. Probability is that size squared, so it is never negative.

Fast animation is not quantum advantage

Typical misconceptionThe browser animation runs fast, so it proves quantum advantage.

Better mental modelThis is a small simulation on a classical computer. The query counts describe this model; they are not measurements on quantum hardware or a complete comparison with classical search.

Run the experiment

01
Watch phase before probability
Choose Before amplification, set one round and inspect its oracle step.
What to observe: The marked amplitude changes sign but its probability does not yet increase.
02
Stop at the peak, then overshoot
Compare Stop near the peak with Go too far.
What to observe: After a few extra rounds, the same targets can become much less likely.
03
Choose a round from the data
Acquire the full round scan.
What to observe: The measured success fractions fluctuate. The round with the highest observed success describes this finite data set; it is not guaranteed to be the best round.
04
Add errors
Try an imperfect oracle and readout flips separately.
What to observe: Coherent phase errors change the amplitudes during the evolution. Readout flips corrupt the reported bit strings after the evolution is over.