QuICS seminar

Quantum mechanics is a statistical theory. It cannot with certainty predict the outcome of all single events, but instead it predicts probabilities of outcomes. This probabilistic nature of quantum theory is at odds with the determinism inherent in Newtonian physics and relativity, where outcomes can be exactly predicted given sufficient knowledge of a system.

The classical capacity of a classical channel is found by maximizing the mutual information between the input and output of a single use of the channel. In contrast, the different capacities of quantum channels are obtained by the infinite regularization of particular entropic quantities. In this talk I will review our current understanding of the need for regularization.

In this talk I will discuss a general method to obtain quantum speedups of classical algorithms which are based on the technique of backtracking, a standard approach for solving constraint satisfaction problems (CSPs). Backtracking algorithms explore a tree whose vertices are partial solutions to a CSP in an attempt to find a complete solution.

Motivated by the phenomenal experimental progress in the coherent control of superconducting resonators, I will describe theoretical progress in how to perform full quantum computation using these devices operating with d (>2) dimensional quantum states (qudits). This progress includes multiple routes to single-qudit logic, entangled state synthesis, and two-qudit logic gates.

In this talk, I will discuss correlations that can be generated by performing local measurements on bipartite quantum systems. I'll present an algebraic characterization of the set of quantum correlations which allows us to identify an easy-to-compute lower bound on the smallest Hilbert space dimension needed to generate a quantum correlation. I will then discuss some examples showing the tightness of our lower bound.

We describe a quantum algorithm that generalizes the quantum linear system algorithm [Harrow et al., Phys. Rev. Lett. 103, 150502 (2009)] to arbitrary problem specifications. We develop a state preparation routine that can initialize generic states, show how simple ancilla measurements can be used to calculate many quantities of interest, and integrate a quantum-compatible preconditioner that greatly expands the number of problems that can achieve exponential speedup over classical linear systems solvers.

Span programs are a model of computation that completely characterize quantum query complexity, and have also been used in some cases to get upper bounds on quantum time complexity. Any span program can be converted to a quantum algorithm that, given an input x, decides whether x is "accepted" by the span program, or "rejected" by the span program.

I'll present a method for estimating the probabilities of outcomes of a quantum circuit using Monte Carlo sampling techniques applied to a quasiprobability representation. This estimate converges to the true quantum probability at a rate determined by the total negativity in the circuit, using a measure of negativity based on the 1-norm of the quasiprobability.

Hamiltonian simulation is a major potential application of quantum computers, because it enables predictions to be made for physical quantum systems, as well as providing a foundation for other quantum algorithms. Standard methods for Hamiltonian simulation involve product formulae, where the Hamiltonian evolution is a product of evolutions for a series of short times. We have developed a range of advanced algorithms with greatly improved performance. One method is to compress product formulae, which gives an exponential improvement in some parameters.