Search Talks

In recent years, the analysis of boolean functions has arisen as an important theme in theoretical computer science. In this talk I will discuss an extension of the concept of a boolean function to quantum computation. It turns out that many important classical results in the theory of boolean functions have natural quantum analogues. These include property testing of boolean functions; the Goldreich-Levin algorithm for approximately learning boolean functions; and a theorem of Friedgut, Kalai and Naor on the Fourier spectra of boolean functions. The quantum generalisation of this theorem uses a quantum extension of the hypercontractive inequality of Bonami, Gross and Beckner. This talk is based on joint work with Tobias Osborne.

Quantum entanglement has two remarkable properties. First, according to Bell\'s theorem, the statistical correlations between entangled quantum systems are inconsistent with any theory of local hidden variables. Second, entanglement is monogamous -- that is, to the degree that A and B are entangled with each other, they cannot be entangled with any other systems. It turns out that these properties are intimately related.

We all know that the EPR argument fails, and we can all provide proofs of one sort or another that it can\'t work. But in spite of this, there\'s something curiously tempting about the reasoning, and the temptation sometimes leads to needless perplexity about other issues. This paper will do two things. It will offer a diagnosis of where the EPR argument goes wrong that shows why we should be suspicious long before we get to Bell-type results, and then use the thought behind this diagnosis to suggest an orientation toward thinking about quantum states. The proposal for understanding states will have some things in common with Bayesian approaches, but will part company with them on some crucial points.

With the aim of proposing feasible, quantum optical realizations of quantum information protocols and minimizing the resource costs in such implementations, we will discuss various, so-called hybrid approaches. These include, for instance, schemes based upon both discrete and continuous quantum variables.

This paper critically examines the view of quantum mechanics that emerged shortly after the introduction of quantum mechanics and that has been widespread ever since. Although N. Bohr, P. A. M. Dirac, and W. Heisenberg advanced this view earlier, it is best exemplified by J. von Neumann’s argument in Mathematical Foundations of Quantum Mechanics (1932) that the transformation of \'a [quantum] state ... under the action of an energy operator . . . is purely causal,\' while, \'on the other hand, the state ... which may measure a [given] quantity ... undergoes in a measurement a non-casual change.\' Accordingly, while the paper discusses all four of these arguments, it will especially focus on that of von Neumann. The paper also offers an alternative, radically noncausal, view of the quantum-mechanical situation and considers the differences between the ensemble and the Bayesian understanding quantum mechanics. It will also discuss the Bayesian approach to quantum information theory in this set of contexts.

Quantum computation by single-qubit measurements was proposed by Raussendorf and Briegel [PRL 86, 5188] as a potential scheme for implementing quantum computers. It also offers an unusual means of describing unitary transformations. To better understand which measurement-based procedures perform unitary operations, we may consider the following problem: under what circumstances can a measurement-based procedure for a unitary U be found, provided a similar procedure for U which relies on post-selection? In this talk, I describe the so-called \'Measurement Pattern Interpolation\' problem, the intuition behind the solved special cases, and possible applications of a general solution to this problem.

Conventional quantum mechanics answers this question by specifying the required mathematical properties of wavefunctions and invoking the Born postulate. The ontological question remains unanswered. There is one exception to this. A variation of the Feynman chessboard model allows a classical stochastic process to assemble a wavefunction, based solely on the geometry of spacetime paths. A direct comparison of how a related process assembles a Probability Density Function reveals both how and why PDFs and wavefunctions differ from the perspective of an underlying kinetic theory. If the fine-scale motion of a particle through spacetime is continuous and position is a single valued function of time, then we are able to describe ensembles of paths directly by PDFs. However, should paths have time reversed portions so that position is not a single-valued function of time, a simple Bernoulli counting of paths fails, breaking the link to PDF\'s! Under certain circumstances, correcting the path-counting to accommodate time-reversed sections results in wavefunctions not PDFs. The result is that a single `switch\' simultaneously turns on both special relativity and quantum propagation. Physically, fine-scale random motion in space alone yields a diffusive process with PDFs governed by the Telegraph equations. If the fine-scale motion includes both directions in time, the result is a wavefunction satisfying the Dirac equation that also provides a detailed answer to the title question.

Many statistics problems involve predicting the joint strategy that will be chosen by the players in a noncooperative game. Conventional game theory predicts that the joint strategy will satisfy an ``equilibrium concept\'\'. The relative probabilities of the joint strategies satisfying the equilibrium concept are not given, and all joint strategies that do not satisfy it are given probability zero. As an alternative, I view the prediction problem as one of statistical inference, where the ``data\'\' includes the details of the noncooperative game. This replaces conventional game theory\'s focus on how to specify a set of equilibrium joint strategies with a focus on how to specify a density function over joint strategies. I explore a Bayesian version of such a Predictive Game Theory (PGT) that provides a posterior density over joint strategies. It is based on the the entropic prior and on a likelihood that quantifies the rationalities of the players. The Quantal Response Equilibrium (QRE) is a popular game theory equilibrium concept parameterized by player rationalities. I show that for some games the local peaks of the posterior density over joint strategies approximate the associated QRE\'s, and derive the associated correction terms. I also discuss how to estimate parameters of the likelihood from observational data, and how to sample from the posterior. I end by showing how PGT can be used to specify a {it{unique}} equilibrium for any noncooperative game, thereby providing a solution to a long-standing problem of conventional game theory.

By storing quantum information in the degenerate ground state of a Hamiltonian, it is hoped that it can be made quite robust against noise processes. We will examine this situation, with particular emphasis on the Toric code in 2D, and show how adversarial effects, either perturbations to the Hamiltonian or interactions with an environment, destroy the stored information extremely quickly.

I show that physical devices that perform observation, prediction, or recollection share an underlying mathematical structure. I call devices with that structure ``inference devices\'\'. I present a set of existence and impossibility results concerning inference devices. These results hold independent of the precise physical laws governing our universe. In a limited sense, the impossibility results establish that Laplace was wrong to claim that even in a classical, non-chaotic universe the future can be unerringly predicted, given sufficient knowledge of the present. Alternatively, these impossibility results can be viewed as a non-quantum mechanical ``uncertainty principle\'\'. Next I explore the close connections between the mathematics of inference devices and of Turing Machines. I end by informally discussing the philosophical implications of these results, e.g., for whether the universe ``is\'\' a computer.

We analyze how quantum complexity poses bounds to the simulation of quantum systems. While methods as Density Functional Theory (DFT) and the Density Matrix Renormalization Group (DMRG) work very well in practice, essentially nothing on the formal requirements is known. In this talk, we consider these methods from a quantum complexity perspective: First, we discuss DFT which encapsulates the difficulty of solving the Schroedinger equation in a universal functional and show that this functional cannot be efficiently computed unless several complexity classes collapse. Second, we consider DMRG, a method to deal with quantum spin chains, and show that even under reasonable assumptions -- a polynomial gap and matrix product ground states -- finding the ground state is still a computationally hard problem. Beyond pinpointing the limitations of the methods, this helps us to understand under which assumptions we might be able to prove their convergence.