QuICS

In this session, we will break out into subgroups to work through the mathematics in the paper "Hidden-State Proofs of Quantumness" (https://arxiv.org/abs/2410.06368).

Each group will have at least one person with familiarity in cryptography familiarity to guide the process.

Participants should read the paper before the session, but are not expected to have grasped all of its concepts.

Experimental control over the strength and angular dependence of interactions between atoms is a key capability for advancing quantum technologies. Here, we use microwave dressing to manipulate and enhance Rydberg-Rydberg interactions in an atomic ensemble. By resonantly coupling opposite parity Rydberg states, we create eigenstates with first-order dipole-dipole interactions. We study the modification of the interactions by measuring the statistics of the light retrieved from the ensemble.

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.