= Opposite-pair elimination for exact quantum balance testing
{title2=$Q(2K)\le K$}
= Opposite-pair elimination
{synonym}
For an even-length Boolean string, one phase query followed by a known <unitary extension> can produce a zero-pair outcome with amplitude proportional to the zero-minus-one imbalance, or an index pair with amplitude proportional to the difference of their phase signs. A zero-pair observation certifies nonbalance. Every nonzero pair has opposite bits, so deleting it preserves the imbalance and allows recursion on two fewer indices. Ending with an empty list certifies balance. This <quantum circuit> is exact on all inputs and uses at most half the original length in queries, even without the constant-or-balanced promise.
Back to article page
