Pith Number

pith:XEM5LDX3

pith:2021:XEM5LDX34M4WNRLIEHBQHPDADT

not attested not anchored not stored refs resolved

Query and Depth Upper Bounds for Quantum Unitaries via Grover Search

Gregory Rosenthal

Any n-qubit unitary can be implemented approximately in time Õ(2^{n/2}) with oracle queries or exactly in circuit depth Õ(2^{n/2}) with ancillae.

arxiv:2111.07992 v5 · 2021-11-15 · quant-ph · cs.CC

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{XEM5LDX34M4WNRLIEHBQHPDADT}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

We prove that any n-qubit unitary can be implemented (i) approximately in time Õ(2^{n/2}) with query access to an appropriate classical oracle, and also (ii) exactly by a circuit of depth Õ(2^{n/2}) with one- and two-qubit gates and 2^{O(n)} ancillae. The proofs involve similar reductions to Grover search.

C2weakest assumption

The existence and query accessibility of an 'appropriate classical oracle' encoding the unitary for part (i), together with the availability of 2^{O(n)} ancilla qubits and the linear-depth arbitrary state preparation subroutine for part (ii); if these modeling assumptions fail or the reductions do not hold, the stated bounds are invalidated. This premise enters directly in the abstract's statement of the two main results.

C3one line summary

Any n-qubit unitary can be implemented approximately with Õ(2^{n/2}) oracle queries or exactly with Õ(2^{n/2}) circuit depth via Grover search reductions, with matching lower bounds for certain implementations.

References

24 extracted · 24 resolved · 7 Pith anchors

[1] Open problems related to quantum query complexity 2021

[2] The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes 2016 · arXiv:1607.05256

[3] Quantum versus classical proofs and advice 2007 · doi:10.4086/toc.2007.v003a007

[4] Quantum lower bounds by quantum arguments 2002 · doi:10.1006/jcss.2002.1826

[5] Quantum Amplitude Amplification and Estimation 2002 · doi:10.1090/conm/305/05215

Cited by

1 paper in Pith

Nonstabilizerness Mpemba Effects

Receipt and verification

First computed	2026-07-01T14:23:04.605215Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

b919d58efbe33966c56821c303bc601cd2d9fa95f2cf80b57c8a0baf98c224fa

Aliases

arxiv: 2111.07992 · arxiv_version: 2111.07992v5 · doi: 10.48550/arxiv.2111.07992 · pith_short_12: XEM5LDX34M4W · pith_short_16: XEM5LDX34M4WNRLI · pith_short_8: XEM5LDX3

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/XEM5LDX34M4WNRLIEHBQHPDADT \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: b919d58efbe33966c56821c303bc601cd2d9fa95f2cf80b57c8a0baf98c224fa

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "ae24996a0fb32001784784d0c4a899dc18a5f4d72ec29096829f2d1b54eb9b59",
    "cross_cats_sorted": [
      "cs.CC"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "quant-ph",
    "submitted_at": "2021-11-15T18:53:48Z",
    "title_canon_sha256": "9aeed3136e1d352ab52bf4ba45341286f245e436b06bc6811ef60edaf2feecaa"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2111.07992",
    "kind": "arxiv",
    "version": 5
  }
}