N/A

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.

In this talk I will first introduce classical and quantum long-range Ising models and their field theory counterparts. I will show that in particular regimes these systems can be described with simple free non-local field theories with dispersion relation $\omega(k)=|k|^{\alpha/2}$.

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.

"Property testers" are algorithms that can efficiently handle very large amounts of data: given a large object that either has a certain property or is somehow “far” from having that property, a tester should efficiently distinguish between these two cases. In this talk we describe recent results obtained for quantum property testing. This area naturally falls into three parts.