N/A

Free lunch served at 11:45

The Boolean constraint satisfaction problem 3-SAT is arguably the canonical NP-complete problem. In contrast, 2-SAT can not only be decided in polynomial time, but in fact in deterministic linear time. In 2006, Bravyi proposed a physically motivated generalization of k-SAT to the quantum setting, defining the problem "quantum k-SAT".

(Free lunch served at 11:45)

We present an algorithm for efficiently approximating qubit unitaries over gate sets derived from totally definite quaternion algebras. The algorithm achieves ε-approximations using circuits of length O(log(1/ε)), which is asymptotically optimal. The algorithm achieves the same quality of approximation as previously-known algorithms for Clifford+T and a few other gate sets. Moreover, the algorithm to compile the efficient approximation is efficient as well: its running time is polynomial in O(log(1/ε)), conditional on a number-theoretic conjecture.

In recent years, Bayesian methods have been proposed as a solution to a wide range of issues in quantum state and process tomography. In this talk, we make these methods practical by solving three distinct problems: numerical intractability, a lack of informative prior distributions, and an inability to track time-dependent processes. Our approach allows for practical computation of point and region estimators for quantum states and channels, and allows tracking of time-dependent states.

Many useful properties of operators can be expressed in terms of their spectral gaps, or the difference in their two smallest eigenvalues. For instance, the spectral gap is relevant to bounding the runtime of an adiabatic optimization algorithm and mixing times of (sub-)stochastic processes, understanding the isoperimetric profile of spaces and rates of heat diffusion, and quantum phase transitions.

How powerful are quantum computers? Despite the prevailing belief that quantum computers are more powerful than their classical counterparts, this remains a conjecture backed by little formal evidence. Shor's algorithm, for instance, gives an example of a problem (factoring), which can be solved efficiently on a quantum computer with no known efficient classical algorithm. Factoring however, is unlikely to be NP-hard, meaning that few unexpected formal consequences would arise, should such a classical algorithm be discovered.

In this talk I will talk about the power of quantum proofs in the framework of quantum query complexity. Specifically, I will discuss the trade-off between the number of queries to an input string and the number of qubits of a quantum proof needed to verify whether the input string possesses a property of interest, and how this trade-off is affected if we only require the algorithm to output the correct answer on a fraction of the inputs.

The Shannon and von Neumann entropies quantify the uncertainty in a system. They are operationally motivated by natural information processing tasks such as compression, channel coding or randomness extraction. In addition to characterizing the fundamental rates at which such tasks can be performed, their additivity properties make them a very valuable tool in applications ranging from complexity theory to many-body systems.

We propose a family of exactly solvable toy models for the AdS/CFT correspondence based on a novel construction of quantum error-correcting codes with a tensor network structure. Our building block is a special type of tensor with maximal entanglement along any bipartition, which gives rise to an exact isometry from bulk operators to boundary operators. The entire tensor network is a quantum error-correcting code, where the bulk and boundary degrees of freedom may be identified as logical and physical degrees of freedom respectively.