56 citations · 210 across the 25 of their papers we have counts for
32 papers
Perfect non-local quantum computation is impossible
Marten Folkertsma, Dmitry Grinko, Gina Muuss +1
Non-local quantum computation (NLQC) asks two parties to apply a joint operation to their quantum inputs using an entangled resource state and one round of simultaneous quantum com…
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…
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…
Quantum position verification in one shot: parallel repetition of the -BB84 and -routing protocols
Llorenç Escolà-Farràs, Florian Speelman
Quantum position verification (QPV) aims to verify an untrusted prover's location by timing communication with them. To reduce uncertainty, it is desirable for this verification to…
Towards experimental demonstration of quantum position verification using true single photons
Kirsten Kanneworff, Mio Poortvliet, Dirk Bouwmeester +6
The geographical position can be a good credential for authentication of a party, this is the basis of position-based cryptography - but classically this cannot be done securely wi…
A quantum cloning game with applications to quantum position verification
Llorenç Escolà-Farràs, Léo Colisson Palais, Florian Speelman
We introduce a quantum cloning game in which separate collaborative parties receive a classical input, determining which of them has to share a maximally entangled state with a…
Fully Characterizing Lossy Catalytic Computation
Marten Folkertsma, Ian Mertz, Florian Speelman +1
A catalytic machine is a model of computation where a traditional space-bounded machine is augmented with an additional, significantly larger, "catalytic" tape, which, while being…
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…
Continuous-variable Quantum Position Verification secure against entangled attackers
Rene Allerstorfer, Llorenç Escolà-Farràs, Arpan Akash Ray +2
Motivated by the fact that coherent states may offer practical advantages it was recently shown that a continuous-variable (CV) quantum position verification (QPV) protocol using c…
Port-Based State Preparation and Applications
Garazi Muguruza, Florian Speelman
We introduce Port-Based State Preparation (PBSP), a teleportation task where Alice holds a complete classical description of the target state and Bob's correction operations are re…
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…
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…
Security of a Continuous-Variable based Quantum Position Verification Protocol
Rene Allerstorfer, Llorenç Escolà-Farràs, Arpan Akash Ray +3
In this work we study quantum position verification with continuous-variable quantum states. In contrast to existing discrete protocols, we present and analyze a protocol that util…
Relating non-local quantum computation to information theoretic cryptography
Rene Allerstorfer, Harry Buhrman, Alex May +2
Non-local quantum computation (NLQC) is a cheating strategy for position-verification schemes, and has appeared in the context of the AdS/CFT correspondence. Here, we connect NLQC…
Oblivious Transfer from Zero-Knowledge Proofs, or How to Achieve Round-Optimal Quantum Oblivious Transfer and Zero-Knowledge Proofs on Quantum States
Léo Colisson, Garazi Muguruza, Florian Speelman
We provide a generic construction to turn any classical Zero-Knowledge (ZK) protocol into a composable (quantum) oblivious transfer (OT) protocol, mostly lifting the round-complexi…
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…
An efficient combination of quantum error correction and authentication
Yfke Dulek, Garazi Muguruza, Florian Speelman
When sending quantum information over a channel, we want to ensure that the message remains intact. Quantum error correction and quantum authentication both aim to protect (quantum…
On the Role of Quantum Communication and Loss in Attacks on Quantum Position Verification
Rene Allerstorfer, Harry Buhrman, Florian Speelman +1
We study the role of quantum communication in attacks on quantum position verification. In this work, we construct the first known example of a QPV protocol that is provably secure…
Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture
Andris Ambainis, Harry Buhrman, Koen Leijnse +2
Classically, for many computational problems one can conclude time lower bounds conditioned on the hardness of one or more of key problems: k-SAT, 3SUM and APSP. More recently, sim…
Memory Compression with Quantum Random-Access Gates
Harry Buhrman, Bruno Loff, Subhasree Patro +1
In the classical RAM, we have the following useful property. If we have an algorithm that uses memory cells throughout its execution, and in addition is sparse, in the sense th…
Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks
Harry Buhrman, Bruno Loff, Subhasree Patro +1
Many computational problems are subject to a quantum speed-up: one might find that a problem having an O(n^3)-time or O(n^2)-time classic algorithm can be solved by a known O(n^1.5…
Towards practical and error-robust quantum position verification
Rene Allerstorfer, Harry Buhrman, Florian Speelman +1
Loss of inputs can be detrimental to the security of quantum position verification (QPV) protocols, as it may allow attackers to not answer on all played rounds, but only on those…
A Guide for New Program Committee Members at Theoretical Computer Science Conferences
Yfke Dulek, Stacey Jeffery, Christian Majenz +3
In theoretical computer science, conferences play an important role in the scientific process. The decisions whether to accept or reject articles is taken by the program committee…
A single-qubit position verification protocol that is secure against multi-qubit attacks
Andreas Bluhm, Matthias Christandl, Florian Speelman
The position of a device or agent is an important security credential in today's society, both online and in the real world. Unless in direct proximity, however, the secure verific…