Computational Bounds for f-Routing

arXiv:2609.40278 · quant-ph, cs.CC · Submitted 2026-09-30 · Read on arXiv

quant-ph, cs.CC

Submitted: 2026-09-30

Updated: 2026-09-30

Terminology

• Fidelity — 64× in this paper · explained in 2 episodes
• Verifier — 21× in this paper · explained in 2 episodes
• Entanglement — 13× in this paper · explained in 3 episodes
• Verification — 13× in this paper · explained in 2 episodes
• Trace — 10× in this paper · explained in 2 episodes
• Stabilizer States — 9× in this paper · explained in 2 episodes
• Quantum State Distinguishability — 6× in this paper
• Sparsity — 5× in this paper · explained in 4 episodes
• Quantum Circuits — 4× in this paper · explained in 2 episodes
• Adversarial Model — 2× in this paper · explained in 1 episode
• Accuracy — 1× in this paper · explained in 1 episode
• Adaptation — 1× in this paper · explained in 1 episode
• Benchmark — 1× in this paper · explained in 2 episodes
• Conditional Disclosure of Quantum Secrets — 1× in this paper

Sources

• Linear gate bounds against natural functions for position-verification
• Rank lower bounds on non-local quantum computation
• Improved Simulation of Stabilizer Circuits
• Conditional disclosure of secrets with quantum resources
• Communication memento: Memoryless communication complexity
• Position-Based Quantum Cryptography: Impossibility and Constructions
• A single-qubit position verification protocol that is secure against multi-qubit attacks
• The Garden-Hose Model
• Simplified instantaneous non-local quantum computation with applications to position-based cryptography
• Code-routing: a new attack on position verification
• A quantum cloning game with applications to quantum position verification
• The Garden Hose Complexity for the Equality Function
• Query Learning Nearly Pauli Sparse Unitaries in Diamond Distance
• QIP = PSPACE
• Quantum Tagging: Authenticating Location via Quantum Information and Relativistic Signalling Constraints
• New Bounds for the Garden-Hose Model
• Complexity and entanglement in non-local computation and holography
• Entanglement cost in non-local quantum computation
• A Tight Lower Bound for the BB84-states Quantum-Position-Verification Protocol
• Device-independence for two-party cryptography and position verification

Related papers

• Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
• Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
• Polynomial-time classical and quantum simulation of quantum impurity models
• Theory of quantum-enhanced interferometry with general Markovian light sources
• A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
• Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity