Pith Number

pith:ZCXPIOJX

pith:2026:ZCXPIOJXUCZ2YBCCQMC6AMEACS

not attested not anchored not stored refs pending

Quantum algorithms for path and cycle containment problems

Amin Shiraz Gilani, Arjan Cornelissen, Subhasree Patro

A dichotomy for path-containment problems shows some are solvable with linear queries while others are equivalent to cycle problems and admit a quantum-walk algorithm with query complexity Õ(n^{3/2 - α_k}) where α_k decays exponentially in k, plus a conditional lower bound.

arxiv:2605.09017 v2 · 2026-05-09 · 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{ZCXPIOJXUCZ2YBCCQMC6AMEACS}

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 a novel quantum-walk-based algorithm that achieves query complexity Õ(n^{3/2-α_k}), where α_k ∈ Θ(c^{-k}) and c = √(3+√17)/2 ≈ 1.33, beating the previous best upper bound O(n^{3/2}).

C2weakest assumption

The randomized reductions between problem variants preserve quantum query complexity up to constant factors; if this fails for any of the listed variants, the claimed equivalence classes and the transfer of the new upper bound would collapse.

C3one line summary

Receipt and verification

First computed	2026-08-06T01:39:39.212058Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

c8aef43937a0b3ac04428305e0308014b38d9a5890402efd6e33a95e52bad89f

Aliases

arxiv: 2605.09017 · arxiv_version: 2605.09017v2 · doi: 10.48550/arxiv.2605.09017 · pith_short_12: ZCXPIOJXUCZ2 · pith_short_16: ZCXPIOJXUCZ2YBCC · pith_short_8: ZCXPIOJX

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/ZCXPIOJXUCZ2YBCCQMC6AMEACS \
  | 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: c8aef43937a0b3ac04428305e0308014b38d9a5890402efd6e33a95e52bad89f

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "524ad259028150913588e47f15c5950571301795f6651ca715380f75aaaa0729",
    "cross_cats_sorted": [
      "cs.CC"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "quant-ph",
    "submitted_at": "2026-05-09T15:55:07Z",
    "title_canon_sha256": "2ccb01834af024729ae4b238dbb890c1dc231e08459666cdf67df4f3d59bebec"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.09017",
    "kind": "arxiv",
    "version": 2
  }
}