Matthias Christandl

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 relatively small loss rates can compromise security. The goal is thus to find protocols that remain secure under practically achievable loss rates. In this work, we modify the usual structure of QPV protocols and prove that this modification makes the potentially high transmission loss between the verifiers and the prover security-irrelevant for a class of protocols that includes a practically-interesting candidate protocol inspired by the BB84 protocol. This modification, which involves photon presence detection, a small time delay at the prover, and a commitment to play before proceeding, reduces the overall loss rate to just the prover’s laboratory. The adapted protocol then becomes a practically feasible QPV protocol with strong security guarantees, even against attackers using adaptive strategies. As the loss rate between the verifiers and prover is mainly dictated by the distance between them, secure QPV over longer distances becomes possible. We also show possible implementations of the required photon presence detection, making the adapted protocol a protocol that solves all major practical issues in QPV. Finally, we discuss experimental aspects and give parameter estimations.

We study a parameterized version of the local Hamiltonian problem, called the weighted local Hamiltonian problem, where the relevant quantum states are superpositions of computational basis states of Hamming weight k. The Hamming weight constraint can have a physical interpretation as a constraint on the number of excitations allowed or the particle number in a system. We prove that this problem is in QW[1], the first level of the quantum weft hierarchy, and that it is hard for QM[1], the quantum analogue of M[1]. Our results show that this problem cannot be fixed parameter quantum tractable (FPQT) unless certain natural quantum analogue of the exponential time hypothesis (ETH) is false.

Abstract Designing encoding and decoding circuits to reliably send messages over many uses of a noisy channel is a central problem in communication theory. When studying the optimal transmission rates achievable with asymptotically vanishing error it is usually assumed that these circuits can be implemented using noise-free gates. While this assumption is satisfied for classical machines in many scenarios, it is not expected to be satisfied in the near term future for quantum machines where decoherence leads to faults in the quantum gates. As a result, fundamental questions regarding the practical relevance of quantum channel coding remain open. By combining techniques from fault-tolerant quantum computation with techniques from quantum communication, we initiate the study of these questions. We introduce fault-tolerant versions of quantum capacities quantifying the optimal communication rates achievable with asymptotically vanishing total error when the encoding and decoding circuits are affected by gate errors with small probability. Our main results are threshold theorems for the classical and quantum capacity: For every quantum channel $T$ and every $\epsilon>0$ there exists a threshold $p(\epsilon,T)$ for the gate error probability below which rates larger than $C-\epsilon$ are fault-tolerantly achievable with vanishing overall communication error, where $C$ denotes the usual capacity. Our results are not only relevant in communication over large distances, but also on-chip, where distant parts of a quantum computer might need to communicate under higher levels of noise than affecting the local gates. Session 2B Stage B