Search by state discrimination

What it fills

• Find the item a check accepts

  Given a way to test candidates and nothing else — no order on the domain, no structure to exploit — return one candidate the test accepts, in fewer queries than looking at them all.

When it applies

The oracle must answer about partial commitments: a query is a pair $(S, y)$ with $S \subseteq [n]$ and $y \in \{0,1\}^{|S|}$, returning $1$ exactly when $x_{S} = y$. The paper puts "no restriction on Hamming weight" on the hidden string, so no promise about it is needed — the power is entirely in the query. Its state-discrimination lemma is proved only in the near-complete regime, "for any $k = n - O(\sqrt{n})$", which is why the algorithm climbs in stages that stay inside it rather than attempting the whole string at once. The authors are explicit about what the method is not: "rather than using amplitude amplification or a quantum walk, our algorithm is ultimately based on the solution to a state discrimination problem." The same paper carries a second algorithm, for combinatorial group testing, whose true quantum query complexity it states is open — "a previous version of this paper claimed an upper bound of $O(\sqrt{k}\,\mathrm{polylog}(k))$ queries, via a reduction to search with wildcards. However, the reduction was incorrect".

Requires

Every step this method names moves its route along, so there is nothing it needs alongside them.

Example

given  an oracle Q_x(S, y) answering whether the hidden n-bit string x agrees
       with the guess y on every position in S                    (Sec. 1.2)

# there is no promise on x -- 'no restriction on Hamming weight'. The strength
# is in the query, which tests a partial guess rather than one position

choose stage sizes n_0 < n_1 < ... < n_l = n with n_{s-1} = ceil(n_s - sqrt(n_s))

# l = O(sqrt(n)) stages, which makes n_0 = O(sqrt(n))

stage 0: query n_0 = O(sqrt(n)) positions directly

for each stage s = 1 ... l:
    apply the unitary that carries knowledge of n_{s-1} positions to a guess
        for n_s of them, built from the pretty good measurement    (Sec. 2, 3)
    verify the guess with one subset query
    while the query answers no:
        binary search with ceil(log n_s) substring queries to locate the wrong
            bits, performed coherently and without measurements, and fix them
        verify again

    # the expected number of wrong bits after the measurement is O(1), by the
    # state-discrimination lemma, so a stage costs an expected O(log n)

return x

# the lemma the stage unitary rests on is proved only for k = n - O(sqrt(n)),
# which is why the algorithm climbs in stages that stay inside that regime
# rather than attempting the whole string at once

# do not read this as amplitude amplification or as a walk. The authors say
# outright that it is neither, and that it rests on a state discrimination
# problem instead

Cost, as the source states it

Theorem 1: $O(\sqrt{n}\log n)$ queries on average to recover the whole string, against a quantum lower bound of $\Omega(\sqrt{n})$ the same theorem proves — a gap of $\log n$ the paper leaves open, calling its algorithm "nearly optimal" rather than optimal. "On average" is defined and is not an average over inputs: "we say that an algorithm 'uses $q$ queries on average' if the expected number of queries it makes on the worst-case input is $q$. We stress that no distribution on the inputs is assumed." The classical floor is $\Omega(n)$ by an information-theoretic argument, and the paper notes that in the standard query model — one position per query — even a quantum algorithm needs $\Omega(n)$. The bill is assembled per stage: $O(\sqrt{n})$ queries in stage zero, then $O(\sqrt{n})$ further stages costing an expected $O(\log n)$ each. For the paper's second problem, combinatorial group testing, Theorem 2 gives $O(k\log k)$ queries against a classical $\Omega(k\log(n/k))$, with a quantum lower bound of only $\Omega(\sqrt{k})$.

Implementations

Nobody has written one up yet. That is a gap in this record, not a statement that the method has never been run — the paper register already records, per paper, which sources report numerics or a hardware run.

What it needs

Nobody has taken this apart yet. That is a gap in this graph, not a claim that the method has no parts.

Other ways to fill the same slot

Different approaches

• Fixed-iteration amplitude rotation

  Start from equal amplitude on every candidate, and alternate two operations — flip the sign of the accepted candidate, then reflect every amplitude about their average. Each round moves a fixed amount of amplitude onto the accepted candidate, so the number of rounds is computed from the domain size before the first query rather than discovered while running.

In the Atlas

• Search with wildcards

  Identify a hidden n-bit string x using an oracle that, for a chosen subset S of the n positions and a string y of length |S|, returns one when the substring of x specified by S equals y and zero otherwise.

Sources

• Quantum algorithms for search with wildcards and combinatorial group testing↗Andris Ambainis, Ashley Montanaro · 2012theory yes · simulation ? · hardware no