{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiguvarvttilqcxiipqa6ndh3ixq4cuwijfmyvyxlt2nraqejtk4ea",
    "uri": "at://did:plc:cx57fsir6oyzywdd4jafsdsw/app.bsky.feed.post/3mpk6wy7kmue2"
  },
  "path": "/papers/q-2026-06-30-2144/",
  "publishedAt": "2026-06-30T09:33:36.000Z",
  "site": "https://quantum-journal.org",
  "tags": [
    "Paper",
    "https://doi.org/10.22331/q-2026-06-30-2144"
  ],
  "textContent": "Quantum 10, 2144 (2026).\n\nhttps://doi.org/10.22331/q-2026-06-30-2144\n\nWe prove that any $n$-qubit unitary can be implemented (i) approximately in time $\\tilde O\\big(2^{n/2}\\big)$ with query access to an appropriate classical oracle, and also (ii) exactly by a circuit of depth $\\tilde O\\big(2^{n/2}\\big)$ with one- and two-qubit gates and $2^{O(n)}$ ancillae. The proofs involve similar reductions to Grover search. The proof of (ii) also involves a linear-depth construction of arbitrary quantum states using one- and two-qubit gates (in fact, this can be improved to constant depth with the addition of fanout and generalized Toffoli gates) which may be of independent interest. We also prove a matching $\\Omega\\big(2^{n/2}\\big)$ lower bound for (i) and (ii) for a certain class of implementations.",
  "title": "Query and Depth Upper Bounds for Quantum Unitaries via Grover Search"
}