QIP 2009 Day 4 Liveblogging

Sorry to those who talked in the afternoon yesterday: I ran off to listen to Michael Nielsen talk at the Santa Fe Institute.

Charles Marcus, “Holding quantum information in electron spins”

Charlie gave a talk about the state of quantum computing in solid state quantum dot systems. Things Charlie talked about:
T1 times of single electron spins of 1 second from Mark Kastner’s group:
arXiv:0707.1656. Those are long, and it would be awesome to have those for real working devices!
Delft’s work on single electron spin manipulations: “Driven coherent oscillations of a single electron spin in a quantum dot”. Nature paper here.
Described early work with using single electron spins where the decoherence times were bad: 10 ns dephasing. This comes from the coupling of the electron spins to the nuclear spin (hyperfine interaction.)
Move to a new model. Use the singlet and triplet states as your qubit. Exchange creates one rotation on this qubit, and a difference in magnetic field creates another rotation on this qubit. One uses a Hahn echo method to boost coherence times up a factor of 1000. This basically works because the nuclear spins are static fields which can be undone by application of an exchange operation, but this is not perfect. This is the “double quantum dot” qubit.
Status report on two qubit gates. They’re made, they’re in the fridge, they’ll soon have nice data. (Nice picture of a double “double quantum dot”) Charlie: the nicer the lithography picture in a talk, the worse the data.)
Described different measurement schemes: at short times, you get a lot of noise, but at longer times, you get less noise but the triplet decays into the singlet. The later measurement can get ninety percent measurement fidelity.
About those nuclear spins. What is the timescale of these changing? Seems very complicated: power law. This is kind of bad because hard to get a handle on how to deal with it.
Cool trick of nuclear polarization with single electron spins. By rapid adiabatic passage and slow adiabatic passage one can perform a process which which does a singlet to triplet manipulation. Conservation of angular momentum then requires flipping of nuclear spin. Great: a way to polarize nuclear spins! But Mhz flipping of nuclear spin only gives nuclear polarizations of 1 percent.
But, wait: if you do this polarization and then look at single decoherence, it gets drastically reduced. That’s good. Called the Zamboni effect. Lasts quite a long time.
Moved on to silicon quantum dots. Still harder to get qubit out of these systems. Different approach: Si/Ge nanowire with integrated charge sensor. Working to get to single electron.
Another approach gate-defined quantum dots on carbon nanotubes. Nice thing is you can control concentration of nuclear spin. Pauli blockage shows big difference between Carbon 12 and Carbon 13. Seem to get really strong hyperfine coupling. Zamboni effect is like 20 minutes in 13 C?

Sandy Irani, “Ground states entanglement in one-dimensional translationally-invariant quantum systems”

Background story: very cool constructions over the last years of one dimensional quantum systems which can be used for universal adiabatic quantum computation (and yield QMA-complete problems.) Work of interest, can this be made translationally invarian? Previous work on this requires initialization because ground state is degnerate. (Nagaj-Wocjan, Janzin-Wocjan-Zhang).
Sandy: Can we make the 1D construction translationally-invariant with a non-degenerate ground state? Not going to solve this here, but instead to talk about entanglement in translationally invariant systems.
Hastings proved an area law for one dimensional systems: arXiv:0705.2024 The bounding area of a contiguous one dimensional segment is just the two end points, so Hastings area law says that the entropy of entanglement is independent of the size of the region. The results gives an entanglement which depends exponentially on one over the energy gap of the system. Gottesman and Hasting raised the question of whether achieving this is possible. Sandy gives a Hamiltonian in 1d which is translationally invariant and where the entanglement scales polynomially in one over the energy gap. This appears in arXiv:0901.1107. A related result is that of Gottesman and Hastings: arXiv:0901.1108 (not translationally invariant, I believe.)

Fernando Brandao (speaker) and Martin Plenio, “Quantum Stein’s lemma for correlated states and asymptotic entanglement transformations”

No paper yet, as far as I can find, on this work. From the abstract:

We present a generalization of quantum Stein’s Lemma to the situation in which the alternative hypothesis is formed by a family of states, which can moreover be non-i.i.d. We consider sets of states which satisfy a few natural properties, the most important being the closedness under permutations of the copies, and determine the rate function of the probability of the error in a very similar fashion to quantum Stein’s Lemma, in terms of the quantum relative entropy.

Steve Flammia (speaker), David Gross, Jens Eisert, Michael Bremner, Andreas Winter, and Caterina Mora, “Most quantum states are useless for measurement-based quantum computation”

Winner of the most coauthors award!
In measurement based quantum computing one starts with an entangled state and then makes a series of interactive measurements which ends up performing a quantum computation. Normally the mantra in quantum computing is that entanglement is good for quantum computing. Here Steve and coauthors showed that this isn’t quite true. They show that for states with large geometric measure (lots of entanglement) are useless for measurement based quantum computation. Turns out this is the vast majority of states (I always like such statements, but they are more interesting, for me, when they can be tied to states we can create, not states “in general.” Just my prejudice. Haar dee Haar Haar.) Paper: arXiv:0810.4331.
Next Steve talked about arXiv:0812.3001. BMW author initials and yet no BMW pictures! First Steve talked about how almost every state there is no poly-bounded classical control circuit which allows a significant advantage over classical polynomial computations, but now from the other direction in terms of being entangled.

Matt “Phelps” Hastings, “Area laws for quantum many-body systems: Gapped one-dimensional systems are in NP”

Matt discussed The following problem: Take a one (spatial) dimensional system with n qubits with nearest neighbor interactions of strength O(1) and local Hilbert space of size O(1), with the promise that (1) the gap between the ground state and first excited satisfies 1/gap=O(1), and (2) either the ground state energy is less than zero or at least 1/poly(n). Decide whether whether the ground state energy is less than zero or at least 1/poly(n). In other words this is a one dimensional quantum system with a constant energy gap. Matt showed that this problem is in NP. Further the certificate for this problem is a matrix product state.
A related problem which Matt discussed which is in P is an adiabatic version of this problem. Here one starts with a trivial Hamiltonian whose ground state is a product state and then adiabatically drags the system to a final Hamitonian, with the Hamiltonian being one dimensional and the gap being constant throughout the adiabatic evolution. Then the above decision problem is in P (ground state less than zero or greater than 1/poly(n)). In other words if there is a way to adiabatically transition from a trivial state to a complicated Hamiltonian with constant gap, then simulating that final system is classically easy.
This is all related to an area law that Matt recently proved: arXiv:0705.2024. Consider a nearest neighbor Hamiltonian in one dimension with interaction strength bounded by J, finite dimensional Hilbert space D, unique ground state, and a spectral gap. Then the entanglement entropy over a continuous region is bounded by S_max=exp(O(v/gap)).

Norbert Schuch (speaker), J. Ignacio Cirac, and Frank Verstraete, “The computational difficulty of finding MPS ground states”

Norbert talked about work on the computational difficulty of finding MPS ground states. Paper: arXiv:0802.3351. In particular Norbert discussed the setup where you have a Hamiltonian in one spatial dimension which is guaranteed to (a) have a unique matrix-product states as its ground state, (b) the spectral gap of the system is 1/poly(n), where n is the number of sites in the system, and (c) the Hamiltonian is frustration free. Surprisingly, even in this setup, the problem of finding the ground state is at least as hard as factoring. If you omit the uniqueness condition and the system can be frustrated ((a) and (c)) then this problem is NP-hard.
Some consequences: the success of density matrix renormalization group (DMRG) cannot be certified in general: in other words you can’t tell whether you have solved the problem of finding the ground states. Another consequence is that DMRG cannot be guaranteed to work even when the Hamiltonian in consideration is frustration free.

Dan Shepherd (speaker) and Michael Bremner, “Instantaneous quantum computation”

The instantaneous quantum computation model is one in which you start in the computational zero state, apply a Hamiltonian which is made up of Pauli X operators, and then make a measurement in the computational basis. This talk tried to convince us that this can produce probability distributions which are not easy to efficiently simulate classically. Paper here: arXiv:0809.0847.
Note, that you can make some money:

Accordingly, we have posted on the internet (http://quantumchallenges.wordpress.com) a $25 challenge problem, of size q = 487, to help motivate further study. This challenge website includes the source code (C) used to make the challenge matrix, and also the source code of the program that we will use to check candidate solutions, excluding only the secret seed value that we used to randomise [sic, this is America, damnit] the problem.

(the sic is mine.)

Jens Eisert and David Gross (speaker), “Lieb-Robinson bounds and ‘supersonic quantum communication'”

Paper here: arXiv:0808.3581. Lieb-Robinson bounds (E.H. Lieb and D.W. Robinson, Commun. Math. Phys. 28, 251
(1972)) limit the propagation speed of information in spin lattices. These bounds have been proven in the case of finite-dimensional models, infinite dimensional models with bounded interaction, and infinite dimensional models with unbounded but harmonic Hamiltonians. Here they show models outside of this setting which violate Lieb-Robinson bounds.

Scott Aaronson (speaker) and John Watrous, “Closed timelike curves make quantum and classical computing equivalent”

Who gave this crazy blogger a spot to talk?
Scott talked about his paper with John Watrous, arXiv:0808.2669 showing that computation (both quantum and classical) with systems that traverse closed time-like curves is PSPACE.
CTC computation works by thinking about qubits or bits which traverse these closed time-like curves and those which don’t (causal qubits or bits). One enforces on the CTC qubits (bits) that there is a consistent quantum density matrix (in the classical case a consistent probability distribution) for the CTC bits, and no such requirement is made on causal qubits (bits.) This model was introduced by David Deutsch in “Quantum mechanics near closed timelike lines.” Phys. Rev. D, 44:3197-3217, 1991. What Scott and John showed was that the model of polynomial time quantum (or classical) computation with access to a polynomial size CTC circuit (either BQP_CTC or BPP_CTC) is equal to PSPACE.
Scott likes to sell this as “If time travel is possible, then quantum computers are no more powerful than classical worlds.” Me I like to think about this “those trying to prove BPP or BQP does not equal PSPACE are trying to disprove time travel”