Seminar

Abstract: Between NISQ (noisy intermediate scale quantum) approaches without any proof of robust quantum advantage and fully fault-tolerant quantum computation, we propose a scheme to achieve a provable superpolynomial quantum advantage (under some widely accepted complexity conjectures) that is robust to noise with minimal error correction requirements. We choose a class of sampling problems with commuting gates known as sparse IQP (Instantaneous Quantum Polynomial-time) circuits and we ensure its fault-tolerant implementation by introducing the tetrahelix code.

Abstract: We discuss recent progress on entanglement catalysis, including the equivalence between catalytic and asymptotic transformations of quantum states and the impossibility to distill entanglement from states having positive partial transpose, even in the presence of a catalyst. A more general notion of catalysis is the concept of entanglement battery. In this framework, we show that a reversible manipulation of entangled states is possible.

Abstract: We show that there exists a unitary quantum oracle relative to which quantum commitments exist but no (efficiently verifiable) one-way state generators exist. Both have been widely considered candidates for replacing one-way functions as the minimal assumption for cryptography—the weakest cryptographic assumption implied by all of computational cryptography. Recent work has shown that commitments can be constructed from one-way state generators, but the other direction has remained open.

Abstract: In this talk I will describe Decoded Quantum Interferometry (DQI), a quantum algorithm for reducing classical optimization problems to classical decoding problems by exploiting structure in the Fourier spectrum of the objective function. (See: https://arxiv.org/abs/2408.08292.) For a regression problem called optimal polynomial intersection, which has been previously studied in the contexts of coding theory and cryptanalysis, we believe DQI achieves an exponential quantum speedup.

Abstract: There has been interest in the dynamics of noninteracting bosons because of the boson sampling problem. These dynamics can be difficult to predict because of the complicated interference patterns that arise due to their indistinguishability. However, if there are unobserved, hidden degrees of freedom, the indistinguishability can be disrupted in the observations. The generalized bunching probability is defined to be the probability that noninteracting bosons undergo linear optical evolution and all arrive in a subset of sites.

Abstract: We present a new method for analyzing and identifying errors in quantum circuits. In our approach, we define the problem using a triple {P}C{Q}, where the task is to determine whether a given set P of quantum states at the input of a circuit C produces a set of quantum states at the output that is equal to, or included in, a set Q. We propose a technique that utilizes tree automata to represent sets of quantum states efficiently, and we develop algorithms to apply the operations of quantum gates within this representation.

Abstract: While the search for quantum advantage typically focuses on speedups in execution time, quantum algorithms also offer the potential for advantage in space complexity. Previous work has shown such advantages for data stream problems, in which elements arrive and must be processed sequentially without random access, but these have been restricted to specially-constructed problems [Le Gall, SPAA `06] or polynomial advantage [Kallaugher, FOCS `21]. We show an exponential quantum space advantage for the maximum directed cut problem.

Abstract: Quantum complexity is emerging as a key property of many-body systems, including black holes, topological materials, and early quantum computers. A state's complexity quantifies the number of computational gates required to prepare the state from a simple tensor product. I will discuss two approaches to better understand the role of quantum complexity in many-body physics. First, we'll consider random circuits, a model for chaotic dynamics. In such circuits, the quantum complexity grows linearly until it saturates at a value exponential in the system size.

Abstract: In recent years, the use of Gottesman-Kitaev-Preskill (GKP) Codes to  implement fault-tolerant quantum computation has gained significant traction and evidence for their experimental utility has steadily grown.  But what does it even mean for quantum computation with the GKP code to be fault tolerant?  In this talk, we discuss the structure of logical Clifford gates for the GKP code and how their understanding leads to a classification of the space of all GKP Codes.

Abstract: In this work we present fast constructions for the quantum Fourier transform and quantum integer multiplication, using few ancilla qubits compared to the size of the input. For the approximate QFT we achieve depth O(log n) using only n + O(n / log n) total qubits, by applying a new technique we call "optimistic quantum circuits." To our knowledge this is the first circuit for the AQFT with space-time product O(n log n), matching a known lower bound. For multiplication, we construct circuits that use no ancilla qubits and only O(n^(1+eps)) gates (for arbitrary eps>0).