Robust sparse IQP sampling in constant depth
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.
Oracle Separation Between Quantum Commitments and Quantum One-wayness
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.
The Weak Generalized Bunching Conjecture
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.
An automata-based approach for quantum circuit/program verification
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.
Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model
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.
GKP Codes: A Rosetta Stone for Quantum Error Correction
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.
Quadratic lower bounds on the stabilizer rank: A probabilistic approach
Abstract: The approximate stabilizer rank of a quantum state is the minimum number of terms in any approximate decomposition of that state into stabilizer states. We expect that the approximate stabilizer rank of n-th tensor power of the “magic” T state scale exponentially in n, otherwise there is a polynomial time classical algorithm to simulate arbitrary polynomial time quantum computations. Despite this intuition, several attempts using various techniques could not lead to a better than a linear lower bound on the “exact” rank.
Stabilization of cat-state manifolds using nonlinear reservoir engineering
Abstract: Reservoir engineering has become valuable for preparing and stabilizing quantum systems. Notably, it has enabled the demonstration of dissipatively stabilized Schrödinger’s cat qubits through engineered two-photon loss which are interesting candidates for bosonic error-corrected quantum computation. Reservoir engineering is however limited to simple operators often derived from weak low-order expansions of some native system Hamiltonians. In this talk, I will introduce a novel reservoir engineering approach for stabilizing multi-component Schrödinger’s cat states.
TBA 5/2/2024
Abstract: TBA
On the optimal error exponents for classical and quantum antidistinguishability
Abstract: The concept of antidistinguishability of quantum states has been studied to investigate foundational questions in quantum mechanics. It is also called quantum state elimination, because the goal of such a protocol is to guess which state, among finitely many chosen at random, the system is not prepared in (that is, it can be thought of as the first step in a process of elimination). Antidistinguishability has been used to investigate the reality of quantum states, ruling out psi-epistemic ontological models of quantum mechanics [Pusey et al., Nat. Phys., 8(6):475-478, 2012].