Q41: What is an SU(2) analogue of Grover search?

Working mathematical formulation

Fix a total-spin sector $\mathcal H_J=V_J\otimes M_J$ and a known, explicitly indexed orthonormal coupling-path basis $\{|x\rangle:x\in[N]\}$ of $M_J$ , with $N=\dim M_J$ . A Boolean function $f:[N]\to\{0,1\}$ has exactly one marked label. Classical queries return $f(x)$ . Quantum queries evaluate the same function coherently on the multiplicity label and an encoded logical answer bit, permitting the invariant phase oracle $O_f=I_{V_J}\otimes\sum_{x=1}^{N}(-1)^{f(x)}|x\rangle\langle x|.$ Find the marked label with probability at least $2/3$ . Give a direct STP implementation with $O(\sqrt N)$ oracle queries, and bound the additional cost of preparation from mixed qubits, pair measurements, adaptive rounds, approximation, and readout.

Scope & assumptions

This benchmark augments STP with a specified black-box oracle; its implementation is not supplied by symmetry. The basis and all non-oracle resources must be independent of the hidden marked label. Count preparation retries and all ancillary qubits. Report oracle-query cost separately from physical implementation cost; if the oracle itself is compiled into measurements, charge that cost as well. Classical controller time is charged over the entire protocol, including all search steps.

Why this is interesting

Grover search is a basic test of whether subsystem spin makes an algorithm easier to understand. We want to see what carries the marked information, what is amplified, and why the process outperforms classical search. “Unstructured” needs an operational definition here; it cannot just mean that we choose measurements randomly.

Established starting point

With coherent access to the phase oracle, the usual construction already fits inside a multiplicity space. Set $\begin{aligned}|u\rangle&=\frac1{\sqrt N}\sum_{x=1}^{N}|x\rangle,\\\rho_u&=\frac{I_{V_J}}{2J+1}\otimes|u\rangle\langle u|.\end{aligned}$ Use $D=I_{V_J}\otimes\bigl(2|u\rangle\langle u|-I_{M_J}\bigr).$ Both $D$ and $O_f$ commute with collective rotations; extend them by the identity outside the chosen sector. Starting from $\rho_u$ , Grover iteration $DO_f$ gives the standard $O(\sqrt N)$ query bound, compared with $\Theta(N)$ randomized classical membership queries. The quantum bound is optimal for unrestricted black-box search. The STP question is how to realize the preparation and reflections, at what cost, or how to obtain the same gain through another measurement protocol.

Explicit variants

What is unstructured?
Keep the coupling-path basis fixed and allow every marked label, with no promise relating it to the path geometry, a subsystem spin, or an interaction graph. The classical comparator can compute on these labels and query $f(x)$ , but receives no additional information about $f$ . Which alternative notions of a marked spin configuration or invariant subspace define a natural search problem? State the oracle and required output anew when there is no classical candidate label.
Preparation and amplification from mixed qubits
Can STP prepare $\rho_u$ to trace-distance error $\varepsilon$ and implement $D$ to diamond-norm error $\varepsilon$ , with overhead polynomial in $n$ and $\log(1/\varepsilon)$ ? Taking $\varepsilon=O(N^{-1/2})$ per iteration controls accumulated error over $O(\sqrt N)$ iterations; since $N\le 2^n$ , logarithmic precision overhead is polynomial in $n$ . Can the complete search use $O(\sqrt N\,\mathrm{poly}(n))$ physical operations, excluding separately charged oracle implementation costs? Include unsuccessful preparation branches. A state maximally mixed on the entire sector is unchanged by every unitary within that sector; useful multiplicity-space coherence must be prepared.
Products of reflections
For a pair, the coherent reflection is $I-2P_s^{ab}=\mathrm{SWAP}_{ab}.$ Products of these bare reflections are qubit permutations. They do not automatically supply the reflection about $|u\rangle$ . Which larger-subsystem projectors, encoded operations, or measurement protocols realize the needed pair of reflections? A projective measurement $\{P_s,P_t\}$ and the unitary $I-2P_s$ are distinct operations; preserve the relative phases needed for the Grover rotation and account for measurement outcomes and any feedforward.
Random swap tests or coordinated schedules
Under the same oracle access and initial-resource conventions, compare uniformly sampled pair measurements, a prescribed sequence of pairs, and schedules that depend on earlier outcomes. Specify where oracle calls occur and what parts of the measurement record are retained. Determine their bounded-error query and measurement costs. Can a random-SWAP protocol amplify the marked component, or does a quadratic advantage require a more coordinated evolution?
What can Schur sampling contribute?
Weak Schur sampling returns $J$ , which is constant in this benchmark and cannot identify a marked multiplicity label. The standard unitary-Schur output retains the $\mathrm{SU}(2)$ irrep factor rather than the coherent multiplicity information used above. Can Schur sampling nevertheless help with preparation, or can a fuller random-SWAP record provide useful search information? Distinguish the declared sampling output, the full measurement transcript, and any quantum state kept for later oracle calls.
Searching for an invariant subspace
For a specified invariant projector $\Pi$ , a known preparation, and initial acceptance probability $a=\mathrm{Tr}(\Pi\rho_0)$ , formulate a task of preparing an accepted state or finding a classical witness. Independent preparation and testing costs $O(1/a)$ trials. Under what access to coherent preparation, its inverse, or reflections can STP achieve an $O(1/\sqrt a)$ dependence? This is an amplification benchmark; a quantum-versus-classical speedup additionally needs a matched classical oracle and task definition.

A place to start

Use six qubits in total spin zero, where $\dim M_0=5$ . Fix the five coupling paths and mark one. Write the uniform multiplicity state, the two reflections, and the changing success probability explicitly. Then replace each assumed operation by an STP protocol, or identify the missing resource. Compare with random pair measurements using the same oracle and initial preparation.

Related work

These works provide context and established results. They need not be the origin of this exact formulation.

Discuss this question

Continue on GitHub Propose a research question

Reading is public. Posting requires a GitHub account. You can also write to Kunal.

Why this is interesting

Explicit variants

What is unstructured?

Preparation and amplification from mixed qubits

Products of reflections

Random swap tests or coordinated schedules

What can Schur sampling contribute?

Searching for an invariant subspace

A place to start

Related work

Related questions

Discuss this question