Seminar

In this work we provide new techniques for a fundamental and ubiquitous task: simulating measurement of a quantum state in the standard basis.  Our algorithms reduce the sampling task to computing poly(n) amplitudes of n-qubit states; unlike previously known techniques they do not require computation of marginal probabilities. First we consider the case where the state of interest is the output state of an m-gate quantum circuit U.

Quantum computing is at an exciting moment in its history, with some high-profile experimental successes in building programmable quantum devices.  That said, these quantum devices (at least in the near term) will be restricted in several ways, raising questions about their power relative to classical computers. In this talk, I will present three results which give us a better understanding of these near-term quantum devices, revealing key features which make them superior to their classical counterparts.

Over the last half-century, theoreticians have outlined a quantum path to provably secure communication, unprecedented sensor sensitivities, and a quantum advantage to solving problems that are classically hard. However, cutting-edge research in quantum algorithms is often detached from exciting progress in quantum hardware engineering. This has created a gap between algorithmic requirements and hardware capabilities.

Quantum computers will reshape the landscape of cryptography. On the one hand, they threaten the security of most modern cryptosystems. On the other, they offer fundamentally new ways to realize tasks that were never before thought to be possible. Crucially, cryptography is also a powerful lens through which to understand quantum computation. In this talk, I will explore the interplay between quantum computation and cryptography, and the many exciting questions at this intersection.

The software system is one essential and critical component in a quantum computing system. However, existing quantum software infrastructures are mainly designed for small-scale quantum computers while they cannot effectively accommodate large-scale quantum computing systems. In this talk, I will first summarize the challenges in designing quantum software systems as the sizes of quantum computer systems continue to grow.

Current semiconductor-based quantum computing approaches rely upon achieving control of nanocircuits at the single-electron level and using them as quantum bits (qubits). Establishing a stable configuration of spins in quantum dot (QD) devices is accomplished by a combination of electrostatic confinement, bandgap engineering, and dynamical control via nearby electrical gates. However, with an increasing number of QD qubits, the relevant parameter space grows exponentially, making heuristic control unfeasible.

The Even-Mansour cipher is a simple method for constructing a (keyed) pseudorandom permutation E from a public random permutation P: {0,1}^n ->{0,1}^n. It is a core ingredient in a wide array of symmetric-key constructions, including several lightweight cryptosystems presently under consideration for standardization by NIST. It is secure against classical attacks, with optimal attacks requiring q_E queries to E and q_P queries to P such that q_P × q_E ≈ 2^n.

Dirac Spin Liquids (DSLs) are gapless symmetric states in 2+1 dimensions with no magnetic order. They are featureless, yet interesting because their low energy physics is believed to be described by QED-3, an effective field theory in terms of gapless Dirac fermions coupled to an emergent U(1) gauge field. They also serve as a parent state for seemingly unrelated magnetically ordered states, where the ordered states arise from condensation of ``monopole excitations” of the DSL. Can such a description have experimentally observable consequences?

Thermodynamics has shed light on engines, efficiency, and time’s arrow since the Industrial Revolution. But the steam engines that powered the Industrial Revolution were large and classical. Much of today’s technology and experiments are small-scale, quantum, far from equilibrium, and processing information. Nineteenth-century thermodynamics requires updating for the 21st century. Guidance has come from the mathematical toolkit of quantum information theory.

Non-local games originated in the 1960s as experiments that can demonstrate behaviors in quantum mechanics that cannot be replicated using classical mechanics alone. Since that time, these games have received considerable attention, partially due to the deep connections between them and other areas of mathematics, such as non-commutative geometry, functional analysis, combinatorics and computational complexity theory.