QuICS

Quantum computing leverages the quantum properties of subatomic matter to enable algorithms to run faster than those possible on a regular computer. Quantum computers have become increasingly practical in recent years, with some small-scale machines available for public use. Quantum computing applications are largely dependent on the software that manipulates computations on the hardware. These applications rely on a variety of symbolic representations including quantum programs to describe and manipulate quantum information effectively.

Quantum mechanics is one of our most profound and successful theoretical frameworks for understanding the physical world. It continues to drive remarkable technological and theoretical breakthroughs, spanning computing, coding theory, cryptography, material science, and chemistry. In this talk, I will describe how the algorithmic lens has been pivotal in rigorously analyzing such quantum systems and revealed deeper structural properties that were previously inaccessible through traditional approaches.

Whether or not a physical system will thermalize from an initial state has been a key question in modern condensed matter physics. Closely related questions are determining whether observables in these systems relax to stationary values, and what those values are. Using tools from computational complexity theory, we demonstrate that given a Hamiltonian on a finite-sized system, determining whether or not it thermalizes or relaxes to a given stationary value is computationally intractable, even for a quantum computer.

Quantum query complexity is a widely studied model for understanding the capabilities and limitations of quantum computers. In this dissertation, we aim to better understand this complexity measure with respect to many natural models that are not well-studied. In particular, we are interested in the following concrete questions.

1) How powerful are quantum computers that could make multiple queries in parallel relative to analogous classical computers?

2) Can there be a simple quantum algorithmic primitive that inherently combines quantum walks and quantum search?

In 1994, the field of quantum computing had a significant breakthrough when Peter Shor introduced a quantum algorithm that factors integers in (probabilistic) polynomial time.  In these talks, I'll explain the mathematical aspects of Shor's algorithm.

Recently an algorithm has been constructed that shows the binary icosahedral group 2I together with a T-like gate forms the most efficient single-qubit universal gate set. To carry out the algorithm fault tolerantly requires a code that implements 2I transversally. We fill this void by constructing a family of distance d = 3 codes that all implement 2I transversally. To do this, we introduce twisted unitary t-groups, a generalization of unitary t-groups under a twisting by an irreducible representation.

A set of universal fault-tolerant logical gates in quantum error correcting codes is necessary for quantum computing. Transversal operations applied independently on each qubit in a code block are naturally fault-tolerant and easy to implement, but the Eastin-Knill theorem states that the resulting discrete gate set cannot be universal. Circumventing this requires complex protocols such as magic state distillation, code switching, etc. Surface code error correction has been demonstrated on several experimental platforms.

The Eastin-Knill theorem shows that the transversal gates of a quantum code, which are naturally fault-tolerant, form a finite group G. We show that G is an invariant of equivalent quantum codes and thus can be considered as a well defined symmetry. This thesis studies how the symmetry G dictates the existence and parameters of quantum codes using representation theory. We focus on qubit quantum codes that have symmetry coming from finite subgroups of SU(2). We examine two different methods of deriving quantum codes from these symmetries.