Conference

Quantum position verification (QPV) was first introduced, under the name quantum tagging, in a patent filed in 2004. It was first discussed in the academic literature in 2009-10. The schemes proposed to that point were shown to be breakable by teleportation attacks in 2010, and a general no-go theorem showing all schemes in this class are breakable was subsequently proved. However, in an alternative standard cryptographic security scenario, in which the tag is assumed to be able to keep classical data secret, unconditionally secure schemes were presented in 2010. The various terminologies and security scenarios highlight important points whose theoretical and practical implications still remain underexplored. In practice, one normally wants to verify the location of a person or valuable object, not of an easily replaceable tagging device, for at least two reasons: (i) the device itself is not so valuable, (ii) adversaries can easily construct a replacement device and thereby potentially spoof the scheme. This requires physical assumptions about the integrity of the tag and its attachment, and bounds on the speed with which the tag may be displaced or destroyed and replaced. QPV schemes that do not rely on such assumptions are breakable without teleportation or non-local computation attacks. In the other direction, when such significant physical assumptions are necessary, it may generally be reasonable to include tag security among them. In this overview I review the early history of QPV and describe various security scenarios and their potential applications. I give versions of the secure 2010 scheme designed for efficient practical implementation and discuss the frequency, accuracy and security of position verification attainable for these schemes with present technology. I also discuss the implied constraints on what may be attainable for QPV schemes involving real-time quantum measurement and/or quantum information processing.

In this talk I will present recent results about the computational complexity of determining homology groups of simplicial complexes, a fundamental task in computational topology. In arXiv:2209.11793 we showed that this decision problem is QMA1-hard. Moreover, we showed that a version of the problem satisfying a suitable promise is contained in QMA. This suggests that the seemingly classical problem may in fact be quantum mechanical. In fact, we were able to significantly strengthen this by showing that the problem remains QMA1-hard in the case of clique complexes, a family of simplicial complexes specified by a graph which is relevant to the problem of topological data analysis. The proof combines a number of techniques from Hamiltonian complexity and homological algebra, and is inspired by a link with supersymmetric quantum mechanics. In this talk I will focus on how the link with supersymmetry inspired the result, and explain the intuition behind the proof.

Recently, Akers et al. proposed a non-isometric holographic map from the interior of a black hole to its exterior. Within this model, we study properties of the black hole S-matrix, which are in principle accessible to observers who stay outside the black hole. Specifically, we investigate a scenario in which an infalling agent interacts with radiation both outside and inside the black hole. Because the holographic map involves postselection, the unitarity of the S-matrix is not guaranteed in this scenario, but we find that unitarity is satisfied to very high precision if suitable conditions are met. If the internal black hole dynamics is described by a pseudorandom unitary transformation, and if the operations performed by the infaller have computational complexity scaling polynomially with the black hole entropy, then the S-matrix is unitary up to corrections that are superpolynomially small in the black hole entropy. Furthermore, while in principle quantum computation assisted by postselection can be very powerful, we find under similar assumptions that the S-matrix of an evaporating black hole has polynomial computational complexity.

The JLMS formula is a cornerstone in our understanding of bulk reconstruction in holographic theories of quantum gravity, best interpreted as a quantum error-correcting code. Moreover, recent work has highlighted the importance of understanding holography as an approximate and perhaps non-isometric code. In this work, we construct an enlarged code subspace for the bulk theory that contains multiple non-perturbatively different background geometries. In such a large holographic code, we carefully derive an approximate version of the JLMS formula from an approximate FLM formula for a class of nice states. We do not assume that the code is isometric, but interestingly find that approximate FLM forces the code to be approximately isometric. Furthermore, we show that the bulk modular Hamiltonian of the entanglement wedge makes important contributions to the JLMS formula and cannot in general be neglected even when the bulk state is semiclassical. Nevertheless, when acting on states with the same background geometry, we find that the modular flow is well approximated by the area flow which takes the geometric form of a boundary-condition-preserving kink transform. We also generalize the results to higher derivative gravity, where area is replaced by the geometric entropy. We conjecture that a Lorentzian definition of the geometric entropy is equivalent to its original, Euclidean definition, and we verify this conjecture in a dilaton theory with higher derivative couplings. Thus we find that the flow generated by the geometric entropy takes the universal form of a boundary-condition-preserving kink transform.

We construct approximately local observables, or "overlapping qubits", using non-isometric maps and show that processes in local effective theories can be spoofed with a quantum system with fewer degrees of freedom, similar to our expectation in holography. Furthermore, the spoofed system naturally deviates from an actual local theory in ways that can be identified with features in quantum gravity. For a concrete example, we construct two MERA toy models of de Sitter space-time and explain how the exponential expansion in global de Sitter can be spoofed with many fewer quantum degrees of freedom and that local physics may be approximately preserved for an exceedingly long time before breaking down. Conceptually, we comment on how approximate overlapping qubits connect Hilbert space dimension verification, degree-of-freedom counting in black holes and holography, approximate locality in quantum gravity, non-isometric codes, and circuit complexity.