8 papers
Making Existing Quantum Position Verification Protocols Secure Against Arbitrary Transmission Loss
Rene Allerstorfer, Andreas Bluhm, Harry Buhrman +4
Signal loss poses a significant threat to the security of quantum cryptography when the chosen protocol lacks loss-tolerance. In quantum position verification (QPV) protocols, even…
Fine-Grained Complexity via Quantum Natural Proofs
Yanlin Chen, Yilei Chen, Rajendra Kumar +2
Buhrman, Patro, and Speelman presented a framework of conjectures that together form a quantum analogue of the strong exponential-time hypothesis and its variants. They called it t…
QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more
Yanlin Chen, Yilei Chen, Rajendra Kumar +2
While seemingly undesirable, it is not a surprising fact that there are certain problems for which quantum computers offer no computational advantage over their respective classica…
Single-qubit loss-tolerant quantum position verification protocol secure against entangled attackers
Llorenç Escolà -Farrà s, Florian Speelman
Protocols for quantum position verification (QPV) which combine classical and quantum information are insecure in the presence of loss. We study the exact loss-tolerance of the mos…
Quantum Catalytic Space
Harry Buhrman, Marten Folkertsma, Ian Mertz +4
Space complexity is a key field of study in theoretical computer science. In the quantum setting there are clear motivations to understand the power of space-restricted computation…
Lossy-and-Constrained Extended Non-Local Games with Applications to Quantum Cryptography
Llorenç Escolà -Farrà s, Florian Speelman
Extended non-local games are a generalization of monogamy-of-entanglement games, played by two quantum parties and a quantum referee that performs a measurement on their local quan…