Seminar

The stabilizer rank of a quantum state ψ is the minimal integer r such that ψ can be written as a linear combination of r stabilizer states. The running time of several classical simulation methods for quantum circuits is determined by the stabilizer rank of the n-th tensor power of single-qubit magic states. In this talk we'll present a recent improved lower bound of Ω(n) on the stabilizer rank of such states, and an Ω(sqrt{n}/log n) lower bound on the rank of any state which approximates them to a high enough accuracy.

The quantum circuit model is the de-facto way of designing quantum algorithms. Yet any level of abstraction away from the underlying hardware incurs overhead. In the era of near-term, noisy, intermediate-scale quantum (NISQ) hardware with severely restricted resources, this overhead may be unjustifiable. We develop quantum algorithms for Hamiltonian simulation "one level below" the circuit model, exploiting the underlying control over qubit interactions available in most quantum hardware implementations.

The connectivity between qubits is one of the many design aspects that go into building a quantum computer. Better connectivity makes it easier to perform arbitrary interacting operations in quantum algorithms, but it may also come with additional noise and may be costly to manufacture. Therefore, many proposals for scalable quantum computer architectures sacrifice connectivity to obtain better modularity and suppress noise. This poses a challenge to running quantum algorithms because simulating missing connectivity can come with significant overhead.

Quantum computers have come a long way since conception, and there is still a long way to go before the dream of universal, fault-tolerant computation is realized. In the near term, quantum computers will occupy a middle ground that is popularly known as the ``Noisy, Intermediate-Scale Quantum'' (or NISQ) regime. The NISQ era represents a transition in the nature of quantum devices from experimental to computational.

Quantifying quantum states’ complexity is a key problem in various subfields of science, from quantum computing to black-hole physics. We prove a prominent conjecture by Brown and Susskind about how random quantum circuits’ complexity increases. Consider constructing a unitary from Haar-random two-qubit quantum gates. Implementing the unitary exactly requires a circuit of some minimal number of gates - the unitary’s exact circuit complexity.

Besides potentially delivering a huge leap in computational power, quantum computers also offer an essential platform for simulating properties of quantum systems.  Consequently, various algorithms have been developed for approximating the dynamics of a target system on quantum computers. But generic quantum simulation algorithms---developed to simulate all Hamiltonians---are unlikely to result in optimal simulations of most physically relevant systems; optimal quantum algorithms need to exploit unique properties of target systems.

Quantum computing is the offspring of quantum mechanics and computer science, two great scientific fields founded in the 20th century. Quantum computing is a relatively young field and is recognized as having the potential to revolutionize science and technology in the coming century. The primary question in this field is essentially to ask which problems are feasible with potential quantum computers and which are not. In this dissertation, we study this question with a physical bent of mind.

We study quantum error correcting codes generated by local random circuits and consider the circuit depth required to achieve high-performance against local error models. Notably, we find that random circuits in D spatial dimensions generate high-performing codes at depth at most O(log N) independent of D. Our approach to quantum code design is rooted in arguments from statistical physics and establishes several deep connections between random quantum coding and critical phenomena in phase transitions.

In recent decades, the rapid development of quantum technologies has led to a new era of programmable platforms, enabling the realizations of quantum simulation and quantum computation.

Fault-tolerant error correction (FTEC), a procedure which suppresses error propagation in a quantum circuit, is one of the most important components for building large-scale quantum computers. One major technique often used in recent works is the flag technique, which uses a few ancillas to detect faults that can lead to errors of high weight and is applicable to various fault-tolerant schemes. In this talk, I will further improve the flag technique by introducing the use of error weight parities in error correction.