This series consists of weekly discussion sessions on foundations of quantum Theory and quantum information theory. The sessions start with an informal exposition of an interesting topic, research result or important question in the field. Everyone is strongly encouraged to participate with questions and comments.
Matchgates are a restricted set of two-qubit gates known to be classically simulable when acting on nearest-neighbor qubits on a path, but universal for quantum computation when the gates can also act on more distant qubits. In this talk, I will address the power of matchgates when they can act on pairs of qubits according to the edges of arbitrary graphs. Specifically, we show that matchgates are universal on any connected graph other than a path or a cycle, and that they are classically simulable on a cycle.
The Bose-Hubbard model is a system of interacting bosons that live on the vertices of a graph. The particles can move between adjacent vertices and experience a repulsive on-site interaction. The Hamiltonian is determined by a choice of graph that specifies the geometry in which the particles move and interact. We prove that approximating the ground energy of the Bose-Hubbard model on a graph at fixed particle number is QMA-complete. In our QMA-hardness proof, we encode the history of an n-qubit computation in the subspace with at most one particle per site (i.e., hard-core bosons).
Although various pieces of indirect evidence about the nature of dark matter have been collected, its direct detection has eluded experimental searches despite extensive effort. If the mass of dark matter is below 1 MeV, it is essentially imperceptible to conventional detection methods because negligible energy is transferred to nuclei during collisions. Here I propose directly detecting dark matter through the quantum decoherence it causes rather than its classical effects such as recoil or ionization.
Quantum codes with
I discuss a technique - the quantum adversary upper bound - that uses the structure of quantum algorithms to gain insight into the quantum query complexity of Boolean functions. Using this bound, I show that there must exist an algorithm for a certain Boolean formula that uses a constant number of queries. Since the method is non-constructive, it does not give information about the form of the algorithm. After describing the technique and applying it to a class of functions, I will outline quantum algorithms that match the non-constructive bound.
TBA
We show that if the ground state energy problem of a
classical spin model is NP-hard, then there exists a choice parameters of the
model such that its low energy spectrum coincides with the spectrum of
\emph{any} other model, and, furthermore, the corresponding eigenstates match
on a subset of its spins. This implies that all spin physics, for example all
possible universality classes, arise in a single model. The latter property was
recently introduced and called ``Hamiltonian completeness'', and it was shown
In a topological
quantum computer, universality is achieved by braiding and quantum information
is natively protected from small local errors. We address the problem of
compiling single-qubit quantum operations into braid representations for
non-abelian quasiparticles described by the Fibonacci anyon model. We develop a
probabilistically polynomial algorithm that outputs a braid pattern to
approximate a given single-qubit unitary to a desired precision. We also
classify the single-qubit unitaries that can be implemented exactly by a
Transversal
implementations of encoded unitary gates are highly desirable for
fault-tolerant quantum computation. It is known, however, that
transversal gates alone cannot be computationally universal. I will show
that the limitation on universality can be circumvented using only
fault-tolerant error correction, which is already required anyway. This
result applies to ``triorthogonal'' stabilizer codes, which were recently
introduced by Bravyi and Haah for state distillation. I will show that
We introduce two relative entropy quantities called the min- and max-relative
entropies and discuss their properties and operational meanings.
These relative entropies act as parent quantities for tasks such as data compression, information
transmission and entanglement manipulation in one-shot information theory. Moreover, they lead us to define entanglement monotones which have interesting operational interpretations.