Qubibyte research note

Rosenthal's Algorithm

Quantum search by decomposition. It finds the same string Grover's algorithm finds, with certainty, in a circuit whose depth does not grow with the register and whose total work grows linearly with the width instead of exponentially.

Depth at 40 qubits 1 round Grover's: 823,549 rounds
Probability of the target 100% exact, not approximate
Work for n wires, blocks of 2 n / 2 checks Grover's: 0.785 · 2n/2
Grover's algorithm 8 qubits, one sealed oracle
round 0 of 12 P(target) = 0.4%
Rosenthal's algorithm 8 qubits, four local oracles
round 0 of 1 P(target) = 0.4%
Amplitude of every basis state of an 8-qubit register, target 10110011 highlighted. Grover's iterate needs 12 rounds to reach 99.99%. Four two-wire blocks reach the target with certainty in one round.

The problem Grover solves

You are given a predicate f on n-bit strings and told that exactly one string x* satisfies f(x*) = 1. Find it. A classical search evaluates f on candidates until one passes, which takes about 2n / 2 evaluations on average. Grover's algorithm (1996) prepares an equal superposition of all 2n strings and repeats a two-step move: mark x* with a phase flip, then reflect every amplitude about the average. Each round moves a little more amplitude onto x*. The number of rounds is about 0.785 · √2n.

Wires Candidates Classical, average Grover's rounds Grover's success

The square root is a real gain. It is also, for a sealed predicate, the end of the road. The next two sections show why, and the ones after that show the door that is still open.

How one round moves the state

All the action lives in a plane spanned by two vectors: the target |x*⟩ and the equal mix of everything else. The starting state sits at an angle β above the "everything else" axis, with sin β = 1 / √N. One round rotates the state by 2β. After k rounds the angle is (2k + 1)β, and the chance of reading the target is sin2 of that angle. You stop as close to 90° as the step size allows.

Candidates N
64
Step angle 2β
14.4°
Rounds k
6
Angle after k rounds
93.4°
P(target)
99.7%
Every round is the same rotation. Small registers overshoot or undershoot 90° because 2β does not divide the quarter turn evenly.

The wall

Bennett, Bernstein, Brassard and Vazirani proved in 1997 that any quantum algorithm which learns about f only by asking it needs on the order of √N questions. Zalka showed in 1999 that Grover's constant is the best possible. The argument is short. Each question can move the state by a bounded amount, and until the algorithm has asked about a candidate, its state cannot depend on whether that candidate is the answer. Telling N candidates apart forces a total movement that no fewer than √N questions can supply. No cleverer sequence of whole-string questions escapes it. The exponent n / 2 is the wall.

Read the fine print, though. The theorem assumes that the only way to learn about f is to ask f about a whole string. That describes a sealed box. It does not describe most predicates people actually search.

Trying to knock the wall down

A fair objection: a lot of people say the bound is proven, but proofs have been wrong before, and nobody has tried every circuit. So we tried, by computer, without assuming anything about what a search circuit should look like. The model is the most general one there is. Between oracle calls the circuit may apply any unitary at all on the search register plus extra ancilla qubits, the oracle may be controlled by an ancilla, and the final measurement may be anything. Every one of those unitaries is a free variable. An optimiser then climbs the success probability, averaged over all possible keys, by gradient ascent on the unitary group. It was started from random circuits and from Grover's own circuit.

Candidates N
64
Queries so far
0
Movement spent
0
Movement allowed, 4k2
0
Keys at the finish line
0 of 64
Why the wall is where it is. Each bar is one possible key, and its height is how far that key, if it were the answer, has moved the state away from the state a blank oracle would produce. To read the key out, its bar has to reach the finish line. The theorem says the squared heights, added over all N keys, cannot exceed 4k2 after k queries. Grover's rounds spend that allowance as evenly as it can be spent, and still need about √N of them. There is no ordering of the keys that changes the sum.

Here is what the optimiser found. For every register size and query count it either landed exactly on Grover's number or on the exact-search number from the phase-matching trick, which uses the same count of queries with a different phase. It never found a circuit that reads the key with fewer queries. Restarts that did not reach Grover's value finished below it, never above. Ancilla qubits and a controlled oracle did not change a single figure.

Keys NQueriesGroverExact search Best circuit found
Success probability of reading the key, averaged over every key, for the best circuit the optimiser could find against the two known algorithms. Dimensions up to 64, with up to two ancilla qubits and a controlled oracle where marked. Where exact search reaches 100%, the optimiser rediscovered it from scratch.

We also asked a smaller question, the one a binary search would need answered first: after a single query, how well can any circuit tell which half of the space the key is in? A halving step needs that answer with certainty.

Keys NQueriesGuessingBest circuit found Needed for a halving step
Learning just the top bit of the key. One membership query cannot even settle the first halving, and the edge over guessing shrinks as the register grows. That is the theorem's bar chart doing its work: after one query the N bars are all short.

Be careful about what this shows. A numerical search finds local peaks, so "nothing better was found" is evidence, not a proof. The proof is the picture above it, and it holds at every size. Anything that beats √N has to change the question the box answers, not the order in which it is asked.

What a binary search would need

A binary search on a sorted list works because one comparison rules out half the candidates. The membership box cannot do that: its answer depends on one string only, so no question you pose to it, in any superposition, carries information about half the keys at once. That is the entire content of the bound. Now change the box. Suppose it answers "how many bits of x agree with the key?" instead of yes or no. Classically that is still a slow game. Each answer is one of n + 1 values, so identifying one of 2n keys takes at least n / log2(n + 1) queries. Quantum mechanically it takes one query, and the key comes out with certainty at any width.

The reason is that the number of mismatched bits is a sum over wires, so a phase that depends on it is a product of one phase per wire. Ask the box with every string at once and a phase of i per mismatched bit, and each wire ends up pointing at +90° if its key bit is 0 and at −90° if it is 1. Those two states are perpendicular, so one rotation and one measurement per wire read the whole key. No search, no rounds, no failure rate. It does not halve the space each step; it takes all n bits in one step.

superposition
Queries
1
Depth
4 gates per wire
P(key)
100%
Grover, membership box
12 rounds, 99.99%
Classical, distance box
at least 3 queries
One query to a distance oracle. Every wire starts on the equator, the oracle turns each one a quarter turn whose direction is its key bit, and the readout maps those two directions to 0 and 1. Type a different key to see the dials follow it.

This is not new either, and the page will not pretend it is. It is the Bernstein and Vazirani construction from 1997 in a different coat, and van Dam showed in 1998 how far the idea goes: with an oracle that returns any function of x and the key, a quantum computer can pull out almost the whole key in about half the classical number of queries. What it does settle is where the "get closer every step" intuition actually lives. It lives in the oracle, not in the search. Give the box a graded answer and the speedup is total. Keep it a yes-or-no box and no ordering of questions gets past √N.

That is why the rest of this page is about the box. The block algorithm that follows keeps a yes-or-no answer but asks it about parts of the string, which is the other honest way to give the box more to say.

Opening the box

A password check compares chunks. A satisfiability formula is an AND of clauses that each touch a few variables. A checksum reads a few bytes at a time. In all of these the predicate is a conjunction of local checks:

f(x) = f1(x on block 1) ∧ f2(x on block 2) ∧ … ∧ fn/b(x on block n/b)

Rosenthal's Algorithm takes the decomposition at face value. It cuts the n wires into blocks of b, gives each block its own oracle that checks only that block's bits, and amplifies every block at the same time on its own wires. A block is a search over 2b items, so the number of rounds depends on b and not on n. With b = 2 every block is done in one round, and the block gate is a plain CZ.

One oracle over all eight wires
The same eight wires. One sealed oracle needs 12 rounds. Four local oracles on disjoint wires run side by side and need one.
  • Depth. k(b) rounds, a constant that does not depend on n. One round for b = 1 or 2, two for b = 3, three for b = 4.
  • Work. (n / b) · k(b) local checks in total, a straight line in n.
  • Result. The target string with probability exactly 1, because every block uses the exact plan described next.

Inside a block: exact instead of approximate

A block of b wires holds N = 2b items, and for small N Grover's plain rounds do not land on 90°. Eight items want 2.6 rounds: two rounds give 94.5%, three overshoot. Long's phase matching (2001) fixes this. Replace the two phase flips, the mark and the reflection, by the same phase φ, chosen so that the effective step shrinks to exactly π / (2k + 1) per round:

sin(φ / 2) = sin(π / (4k + 2)) / sin β,   k = ⌈π / (4β) − 1/2⌉

After k rounds the block is at its target with probability exactly 1. For b = 2 the matched phase is π, which is why that case needs nothing but CZ gates.

Items in the block
8
Rounds k
2
Matched phase φ
0.677π
Plain rounds land at
104°
P(target), plain rounds
94.5%
P(target), matched
100%
Same number of rounds, two different landings. The plain step keeps its size and misses; the matched step is trimmed so that k of them end exactly on the target axis.
Block size b Items Rounds Matched phase Block gate

The plan for any width

Width n and block size b give ⌊n / b⌋ full blocks and, when b does not divide n, one smaller tail block with its own matched plan. A smaller block never needs more rounds, so the tail never adds depth. Move the sliders and compare with Grover's rounds for the same width.

Layout
Depth (rounds)
Local checks
Block phase
P(target)100%
Grover's rounds
Grover's success
Rounds saved

Scaling

Grover's rounds double every two wires. Rosenthal's depth is flat and its local work is a straight line. The vertical axis is logarithmic, which is the only way to fit both on one chart.

Rounds against register width, 2 to 64 wires. Hover for exact values.

The circuit

Eight wires, blocks of two. Hadamards first. Then the block oracles: an X on every wire whose target bit is 0, one CZ per block, and the X gates again. Then block diffusion: H, X, the same four CZ gates, X, H. Fifty-four gates, one round, and the register reads the target every time. Change the target and watch the X gates move.

8 bits, least significant bit on wire 0 Superposition
54 gates. Every CZ touches only its own block.

What this claims, and what it does not

  • The black-box lower bound stands. Rosenthal's Algorithm never asks the whole predicate as one box; it asks the parts. If a predicate has no parts, such as a cryptographic hash or a random function, there is nothing to decompose and √N is still the price. In Qubibyte, Exact Search and Early-Stop Search are the tools for that case.
  • We tried to break it and could not. An optimiser over every circuit shape, with ancilla qubits and a controlled oracle, never read the key with fewer queries than Grover or exact search at any size it could reach, and a single query never settled even the first bit. The details are in the attack section above.
  • A graded oracle changes everything. If the box reports how many bits agree instead of yes or no, one query finds the key with certainty at any width. That is the Bernstein and Vazirani idea, and it is where the "get closer each step" intuition belongs.
  • Against Grover's on a decomposable predicate the gain is exponential in both depth and work: one round against 823,549 at 40 wires with b = 2, and n / 2 local checks against 0.785 · 220 oracle calls.
  • Decomposition helps classical solvers too. A classical search that also sees the parts needs at most 2b evaluations per block, so linear work in n as well. The quantum advantage lives inside a block: fewer local checks than the classical count, and a landing with no failure rate. Stoudenmire and Waintal made a related point in 2024: given the oracle's source code, a classical method can complete Grover's task with linearly many simulated oracle calls.
  • What would break it. Constraints that overlap, such as a clause touching wires in two different blocks. Then the blocks are not independent and the per-block plan is no longer exact. Handling overlap without giving up exactness is the open problem this page leaves on the table.

Try it in Qubi

Rosenthal, ExactSearch, FastSearch and Grover are all in the standard library of the Qubibyte simulator. Each of the lines below is a complete program on its own.

bitstring key = 0b101010011

Rosenthal(key)        // four CZ blocks and a one-wire tail: 1 round, certainty
Rosenthal(key, 3)     // three blocks of three: 2 rounds, certainty
ExactSearch(key)      // one sealed oracle with phase matching: 18 rounds, certainty
Grover(key)           // one sealed oracle: 17 rounds, 99.94%

The distance-oracle circuit from the binary search section is short enough to write out by hand. It is a complete program for the default eight wires. S is the phase gate P(π/2), and the X gates before and after it put the phase on the mismatching side of each wire.

bitstring key = 0b10110011
n = len(key)
ones = tolist(key)
ANNOTATE 0..(n-1) "Uniform superposition"
H (0..(n-1))
ANNOTATE 0..(n-1) "Distance oracle: phase i per mismatched bit" "dist"
X (ones)
S (0..(n-1))
X (ones)
ENDANNOTATE "dist"
ANNOTATE 0..(n-1) "Read out"
SDG (0..(n-1))
H (0..(n-1))
Open the simulator Read the Qubi docs

References

  1. L. K. Grover, "A fast quantum mechanical algorithm for database search", STOC 1996. arXiv:quant-ph/9605043
  2. C. H. Bennett, E. Bernstein, G. Brassard, U. Vazirani, "Strengths and weaknesses of quantum computing", SIAM J. Comput. 26, 1997. arXiv:quant-ph/9701001
  3. E. Bernstein, U. Vazirani, "Quantum complexity theory", SIAM J. Comput. 26, 1997.
  4. W. van Dam, "Quantum oracle interrogation: getting all information for almost half the price", FOCS 1998. arXiv:quant-ph/9805006
  5. C. Zalka, "Grover's quantum searching algorithm is optimal", Phys. Rev. A 60, 1999. arXiv:quant-ph/9711070
  6. M. Boyer, G. Brassard, P. Høyer, A. Tapp, "Tight bounds on quantum searching", Fortschritte der Physik 46, 1998. arXiv:quant-ph/9605034
  7. G. L. Long, "Grover algorithm with zero theoretical failure rate", Phys. Rev. A 64, 2001. arXiv:quant-ph/0106071
  8. N. J. Cerf, L. K. Grover, C. P. Williams, "Nested quantum search and structured problems", Phys. Rev. A 61, 2000. arXiv:quant-ph/9806078
  9. K. Zhang, V. E. Korepin, "Depth optimization of quantum search algorithms beyond Grover's algorithm", Phys. Rev. A 101, 2020. arXiv:1908.04171
  10. T. J. Yoder, G. H. Low, I. L. Chuang, "Fixed-point quantum search with an optimal number of queries", Phys. Rev. Lett. 113, 2014. arXiv:1409.3305
  11. E. M. Stoudenmire, X. Waintal, "Opening the black box inside Grover's algorithm", Phys. Rev. X 14, 2024. arXiv:2303.11317
  12. K. Zhang, H.-L. Shi, X.-H. Wang, V. Korepin, "Palindromic structure of depth-efficient quantum search algorithms", 2026. arXiv:2606.00960