Publicly Verifiable Quantum Money from Random Lattices
Publicly verifiable quantum money is a protocol for the preparation of quantum states that can be efficiently verified by any party for authenticity but is computationally infeasible to counterfeit. We develop a cryptographic scheme for publicly verifiable quantum money based on Gaussian superpositions over random lattices.
Uncertainty Relations from Graph Theory
Quantum measurements are inherently probabilistic. Further defying our classical intuition, quantum theory often forbids us to precisely determine the outcomes of simultaneous measurements. This phenomenon is captured and quantified through uncertainty relations. Although studied since the inception of quantum theory, this problem of determining the possible expectation values of a collection of quantum measurements remains, in general, unsolved.
Strong converse bounds for compression of mixed states
The optimal rates for compression of mixed states was found by Koashi and Imoto in 2001 for the blind case and by Horodecki and independently by Hayashi for the visible case respectively in 2000 and 2006. However, it was not known so far whether the strong converse property holds for these compression problems. In this work, we show that the strong converse holds for the blind compression scheme. For the visible scheme, the strong converse holds up to the continuity of the regularized Renyi entanglement of purification.
A sufficient family of necessary inequalities for the quantum marginals problem
The quantum marginals problem (QMP) aims to understand how the various marginals of a joint quantum state are related to one another by deciding whether or not a given collection of marginals is compatible with some joint quantum state. Although existing techniques for the QMP are well developed for the special case of disjoint marginals, the same is not true for the generic case of overlapping marginals. The leading technique for the generic QMP, published by Yu et. al. (2021), resorts to evaluating a hierarchy of semidefinite programs.
Tight bounds for Quantum Learning and Testing without Quantum Memory
In this talk, we consider two fundamental tasks in quantum state estimation, namely, quantum tomography and quantum state certification. In the former, we are given n copies of an unknown mixed state rho, and the goal is to learn it to good accuracy in trace norm. In the latter, the goal is to distinguish if rho is equal to some specified state, or far from it. When we are allowed to perform arbitrary (possibly entangled) measurements on our copies, then the exact sample complexity of these problems is well-understood.
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
The Quantum Singular Value Transformation (QSVT) is a recent technique that gives a unified framework to describe most quantum algorithms discovered so far, and may lead to the development of novel quantum algorithms. In this paper we investigate the hardness of classically simulating the QSVT. A recent result by Chia, Gilyén, Li, Lin, Tang and Wang (STOC 2020) showed that the QSVT can be efficiently "dequantized" for low-rank matrices, and discussed its implication to quantum machine learning.
LDPC Quantum Codes: Recent developments, Challenges and Opportunities
Quantum error correction is an indispensable ingredient for scalable quantum computing. We discuss a particular class of quantum codes called "quantum low-density parity-check (LDPC) codes." The codes we discuss are alternatives to the surface code, which is currently the leading candidate to implement quantum fault tolerance. We discuss the zoo of quantum LDPC codes and discuss their potential for making quantum computers robust with regard to noise.
Interactive Proofs for Synthesizing Quantum States and Unitaries
Whereas quantum complexity theory has traditionally been concerned with problems arising from classical complexity theory (such as computing boolean functions), it also makes sense to study the complexity of inherently quantum operations such as constructing quantum states or performing unitary transformations.
Universal efficient compilation: Solovay-Kitaev without inverses
The Solovay-Kitaev algorithm is a fundamental result in quantum computation. It gives an algorithm for efficiently compiling arbitrary unitaries using universal gate sets: any unitary can be approximated by short gates sequences, whose length scales merely poly-logarithmically with accuracy. As a consequence, the choice of gate set is typically unimportant in quantum computing. However, the Solovay-Kitaev algorithm requires the gate set to be inverse-closed.
Post-quantum security of the Even-Mansour cipher
The Even-Mansour cipher is a simple method for constructing a (keyed) pseudorandom permutation E from a public random permutation P: {0,1}^n ->{0,1}^n. It is a core ingredient in a wide array of symmetric-key constructions, including several lightweight cryptosystems presently under consideration for standardization by NIST. It is secure against classical attacks, with optimal attacks requiring q_E queries to E and q_P queries to P such that q_P × q_E ≈ 2^n.