Southwest Quantum Information and Technology
Eleventh Annual Meeting, February 19-22, 2009
Seattle, Washington
Full Program | Thursday | Friday | Saturday | Sunday
| SESSION 8: Breakout I - Quantum Information Theory | Session Chair: |
| 3:30-4:00 | Rodney Van Meter, Keio University | Resource Handling for Quantum Networks of Arbitrary Topology | Abstract. To date, research on entangled quantum networks has primarily focused on an abstract model consisting of a linear chain of repeaters, with a power of two number of hops of identical length and quality. We are analyzing the behavior of more complex network topologies, with more than two end nodes competing to communicate across shared links. We compare three resource management disciplines, hop-by-hop teleportation, nested entanglement swapping, and graph state-based bipartite communication. We discuss quantum equivalents to the classical network concepts of spatially and temporally multiplexed circuit switching, and packet switching. We show cases in which multiplexing raises the aggregate communication rate, and cases in which graph states help the system reach the bisection bandwidth. |
| 4:00-4:30 | Sevag Gharibian, Institute for Quantum Computing, University of Waterloo | Strong NP-Hardness of the Quantum Separability Problem | Abstract. Quantum entanglement is generally believed to be a valuable resource in the theory of quantum computing. The problem of determining whether an arbitrary quantum state is entangled, dubbed the Quantum Separability problem, has hence received much attention over the past decade. In 2003, Gurvits showed that the Quantum Separability problem is NP-hard, with one caveat - one must allow instances in which the input quantum state is exponentially close (with respect to dimension, and in Euclidean distance) to the border of the set of separable (equivalently, unentangled) quantum states. This leaves open the question - is the Quantum Separability problem "weakly" NP-hard, i.e. can it be solved efficiently if one is promised that the input state is at least an inverse polynomial distance away from the border of the separable set? In this talk, we answer this question negatively by showing that the Quantum Separability problem is in fact "strongly" NP-hard. This is accomplished by combining previous work by Gurvits and a recent non-ellipsoidal reduction of Liu to show that the Weak Membership problem over the set of separable quantum states is strongly NP-hard. Based on this result, we observe an immediate lower bound on the maximum distance possible between a bound entangled state and the separable set (assuming P != NP). Time permitting, we also demonstrate that determining whether a completely positive trace-preserving linear map (i.e. a quantum channel) is entanglement-breaking is NP-hard. |
| 4:30-5:00 | Soraya Taghavi, University of Southern California | Channel-Optimized Quantum Error Correction | Abstract. We develop a theory for finding quantum error correction (QEC) procedures which are optimized for given noise channels. Our theory accounts for uncertainties in the noise channel, against which our QEC procedures are robust. We demonstrate via numerical examples that our optimized QEC procedures always achieve a higher channel fidelity than the standard error correction method, which is agnostic about the specifics of the channel. Our main novel finding is that in the setting of a known noise channel the recovery ancillas are redundant for optimized quantum error correction. We show this using a general rank minimization heuristic and supporting numerical calculations. Therefore, one can further improve the fidelity by utilizing all the available ancillas in the encoding block. |
| 5:00-5:30 | Beni Yoshida, Massachusetts Institute of Technology | Duality theorem and topological properties in local stabilizer codes | Abstract. Beni Yoshida Massachusetts Institute of Technology Abstract. Topological codes offer the possibility of a naturally fault-tolerant quantum memory, and significant progress has been made with theoretical constructions in four dimensions. However, recent work (Bravyi and Terhal; Kay and Colbeck) has ruled out the possibility of such memories in two-dimensions, and left an open question about three-dimensional topological codes. Specifically, Bravyi and Terhal show that the distance of geometrically local stabilizer codes in a D-dimensional lattice of volume LD is bounded above by O(LD - 1). Here, we present a new approach to the problem, which sharpens these bounds, by limiting consideration to topological codes whose stabilizers are geometrically local and have translational symmetry. Using this physically reasonable assumption, and assuming that the number of logical qubits is a small number which is independent of the lattice size, we find that the logical qubits must obey a duality theorem, whereby each logical qubit may be described by a pair of weight O(La) and O(LD - a) logical operators. This gives a full set of relations between all logical operators. It follows from this theorem that the distance of such codes is bounded above by O(Ln) for 2n- and (2n+1)-dimensional lattices. This non-trivial duality clearly distinguishes systems of even and odd dimension. One surprising consequence is that for certain definitions of topological protection, encodings are possible only in systems of even dimension. This is consistent with a fact in topological quantum field theory, that the quantum Hall effect can occur only in systems of even dimension. We illustrate the implications of this observation by showing that on a two-dimensional Bravais lattice with a small number of encoded qubits, all the logical operators have O(L) weight, such that all the logical qubits are topologically protected from local errors. This also allows us to directly relate the number of encoded qubits with the topological entropy, providing insights which will be useful in designing gapped Hamiltonians with topological properties which may be useful for quantum memories. [1] Sergey Bravyi and Barbara M. Terhal, "A no-go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes", arXiv:0810.1983 (2008)[2] Alastair Kay and Roger Colbeck, "Quantum Self-Correcting Stabilizer Codes", arXiv:0810.3557 (2008) |