56 citations · 210 across the 25 of their papers we have counts for
29 papers · 1 filter
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…
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…
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 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…
The Quantum Strong Exponential-Time Hypothesis
Harry Buhrman, Subhasree Patro, Florian Speelman
The strong exponential-time hypothesis (SETH) is a commonly used conjecture in the field of complexity theory. It states that CNF formulas cannot be analyzed for satisfiability wit…
Round elimination in exact communication complexity
Jop Briët, Harry Buhrman, Debbie Leung +2
We study two basic graph parameters, the chromatic number and the orthogonal rank, in the context of classical and quantum exact communication complexity. In particular, we conside…
Asymptotic performance of port-based teleportation
Matthias Christandl, Felix Leditzky, Christian Majenz +3
Quantum teleportation is one of the fundamental building blocks of quantum Shannon theory. While ordinary teleportation is simple and efficient, port-based teleportation (PBT) enab…