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".

An oracle that accepts a subset $S$ of the $n$ positions together with a guess $y$ for those positions, and answers whether the hidden string agrees with $y$ on every position in $S$ — as the unitary $|S\rangle|y\rangle|z\rangle \mapsto |S\rangle|y\rangle|z \oplus Q_{x}(S, y)\rangle$. No promise on the hidden string is required.

1. Marking oracle over a domain → A marked item, with its query billgrow the known prefix by discriminating states

   The object measured at each stage is a family of states indexed by the hidden string: $|\psi_{x}^{k}\rangle := \frac{1}{\sqrt{\binom{n}{k}}} \sum_{S \subseteq [n],\, |S| = k} |S\rangle |x_{S}\rangle$, with $|x_{S}\rangle := \bigotimes_{i \in S} |x_{i}\rangle$. Recovering $x$ from one copy is a state discrimination problem, and it is solved by the pretty good measurement: for a set $\{|\varphi_{i}\rangle\}$ set $\rho = \sum_{i} |\varphi_{i}\rangle\langle\varphi_{i}|$ and take $|\mu_{i}\rangle := \rho^{-1/2}|\varphi_{i}\rangle$, the inverse taken on the support of $\rho$; this is a POVM because $\sum_{i} |\mu_{i}\rangle\langle\mu_{i}| = \rho^{-1/2}\left(\sum_{i}|\varphi_{i}\rangle\langle\varphi_{i}|\right)\rho^{-1/2} = I$, and it outputs $j$ on input $|\varphi_{i}\rangle$ with probability exactly $|\sqrt{G}_{ij}|^{2}$ for $G$ the Gram matrix. Here the Gram matrix depends only on the Hamming distance, $G_{xy} = \langle\psi_{x}^{k}|\psi_{y}^{k}\rangle = \binom{n - d(x,y)}{k} \big/ \binom{n}{k}$, so it is diagonalised by the Fourier transform over $\mathbb{Z}_{2}^{n}$ and its eigenvalues are $\lambda(s) = 2^{n-k}\binom{n - |s|}{n - k} \big/ \binom{n}{k}$, an identity of Delsarte. assumption: the measurement is optimal, not merely convenient — the states are geometrically uniform, being generated from $\sum_{S}|S\rangle|0\rangle$ by the abelian group $\{U_{y}\}$ with $U_{y}|S\rangle|x\rangle = |S\rangle|x + y_{S}\rangle$, and for such families the pretty good measurement minimises the average error. What the measurement buys is stated as a distance rather than as a success probability: for $k = n - O(\sqrt{n})$ it outputs $\tilde{x}$ with expected Hamming distance $d(x, \tilde{x}) = O(1)$. approximation: the measurement alone does not return $x$. What it returns is a guess wrong in $O(1)$ places on average, and it is the verification query and the coherent binary search over $\lceil\log n_{s}\rceil$ substring queries after it that make the stage exact — which is why the query count carries a $\log n$ the lower bound does not. The paper states the gain per query — "with one query, we can increase the knowledge about the input $x$ from $k$ bits to $k + \Theta(\sqrt{k})$ bits" — and a stage spends that one query plus the repair above it, so $O(\sqrt{n})$ stages of an expected $O(\log n)$ queries each reach $n$.

   approximationassumption

The hidden $n$-bit string in full — every stage ends on an oracle answer confirming it, so what is uncertain here is the bill and not the answer — together with the expected number of queries spent on the worst-case input.

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

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})$.

• Search with wildcards · Qiskit

  From the repository — run, not written up from a paper · unsupported

  About

  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.

  Methods

  None found yet.

  Data

  None found yet.

  Code

  Qiskit

  Results

  Literature record · problem statement and speedup class checked against the Quantum Algorithm Zoo entry · primary reference checked against its arXiv abs page

• 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.