Quantum query complexity of symmetric Boolean functions

A quantum query algorithm accesses an unknown bit string through an oracle. This problem asks how many queries it needs to compute a Boolean function whose value depends only on the number of 1s.

Why it matters and what counts as progress

Why it matters: The paper answers the lower-bound question and identifies the order of the additive overhead for symmetric Boolean functions.

What counts as progress: Upper and lower bounds should specify whether the output is one Boolean value or the exact Hamming weight and state the permitted error.

How the problem developed

  1. 13 May 2014 · Development [1]

    Shelby Kimmel, as reported by Scott Aaronson Asked whether any n-bit Boolean function could need more than n/2n/2 quantum queries at bounded error.

  2. 6 Nov 2026 · Proof [2][3][4]

    Yuan Deng and colleagues Gave a symmetric Boolean family requiring an additive n(1/3)n^{(1/3)} query overhead and a matching-order upper bound for Hamming weight.

AI contribution

Beyond the n/2n/2 Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions

Yuan Deng, Zihan Hao, Honghao Lin, Qipeng Liu, Vahab Mirrokni, Jianan Shao, David P. Woodruff

An explicit family of symmetric n-bit Boolean functions needs n/2+Ω(n(1/3))n/2 + \Omega (n^{(1/3)}) quantum queries at sufficiently small fixed error. The same paper gives a quantum algorithm that recovers exact Hamming weight with n/2+O(n(1/3))n/2 + O(n^{(1/3)}) queries at bounded error.

AI involvementAI-led
ImportanceNotable
Technical verificationPartial
Human understandingPartial
Paper date:

Sources

  1. Aaronson’s 2014 open-question list, question 5
  2. Original manuscript
  3. AI methodology
  4. Lean artifact for the initial lower bound
  5. Authors’ lower-bound analysis
Publication history