Bulletin of the American Physical Society
APS March Meeting 2010
Volume 55, Number 2
Monday–Friday, March 15–19, 2010; Portland, Oregon
Session D4: Quantum Computer Science |
Hide Abstracts |
Sponsoring Units: GQI Chair: Dave Bacon, University of Washington Room: Oregon Ballroom 204 |
Monday, March 15, 2010 2:30PM - 3:06PM |
D4.00001: Surprises in the theory of quantum communications Invited Speaker: Graeme Smith Notions of communication and computation are most naturally formulated in the quantum arena. Unlike the stuff of conventional communication theory, quantum information cannot be copied, nor eavesdropped on without disturbance, and it can mediate the intense and private form of correlation known as entanglement. As in classical information theory, quantum capacity has to do with sphere packing, but in $C_2^{\otimes n}$ rather than $Z_2^{n}$. This difference gives rise to a much richer theory. For example, in contrast to what happens classically, here we often find strong nonadditivity of capacity---the capacity of two channels used together can be much larger than the sum of the individual capacities. [Preview Abstract] |
Monday, March 15, 2010 3:06PM - 3:42PM |
D4.00002: A quantum algorithm for solving linear systems of equations Invited Speaker: Aram Harrow Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix A and a vector b, find a vector x such that Ax=b. We consider the case where one doesn't need to know the solution x itself, but rather an approximation of the expectation value of some operator associated with x, e.g., x'Mx for some matrix M. In this case, when A is sparse, N by N and has condition number kappa, classical algorithms can find x and estimate x'Mx in O(N sqrt(kappa)) time. Here, we exhibit a quantum algorithm for this task that runs in poly(log N, kappa) time, an exponential improvement over the best classical algorithm.\\[4pt] This talk is based on arXiv:0811.3171, which is joint work with Avinatan Hassidim and Seth Lloyd. [Preview Abstract] |
Monday, March 15, 2010 3:42PM - 4:18PM |
D4.00003: Span programs and optimal quantum query algorithms Invited Speaker: Ben Reichardt We show that the general adversary lower bound on quantum query complexity is nearly tight, by giving a matching quantum walk algorithm. The result gives a new semi-definite program for quantum query complexity, and shows an equivalence to the span program model of computation. Span programs compose easily, and this yields a quantum recursion method. Classical algorithms cannot compose in this way. Applying the technique to solve problems defined recursively with independent inputs, i.e., to evaluating formulas, gives an optimal quantum formula-evaluation algorithm. Span programs are a promising model for developing more quantum algorithms. [Preview Abstract] |
Monday, March 15, 2010 4:18PM - 4:54PM |
D4.00004: The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems Invited Speaker: Sandy Irani Recent results have shown that the problem of computing ground energies for one-dimensional quantum systems is likely to be computationally difficult in general, even for a quantum computer. These results establish hardness by showing that the solution to a 1D ground energy problem can encode the solution to an arbitrary problem in the class quantum NP. The particular Hamiltonians that result from these reductions, however, are highly non-physical in that each local term depends on its position in the one-dimensional chain. By contrast, many systems of physical interest are translationally-invariant. In this talk, we will show that computing the ground energy of translationally-invariant quantum systems is likely to be computationally intractable as well, even for quantum computers. The classical counterpart to the quantum ground energy problem is a tiling problem which has been studied in the computer science literature. Hardness results were known for tiling but not in the translationally-invariant case. We establish the hardness of classical two-dimensional translationally-invariant tiling. Joint work with Daniel Gottesman [Preview Abstract] |
Monday, March 15, 2010 4:54PM - 5:30PM |
D4.00005: Unconditional security from noisy quantum storage Invited Speaker: Stephanie Wehner We consider the implementation of two-party cryptographic primitives based on the sole \emph{physical} assumption that no large-scale reliable quantum storage is available to the cheating party. An important example of such a task is secure identification. Here, Alice wants to identify herself to Bob (possibly an ATM machine) without revealing her password. More generally, Alice and Bob wish to solve problems where Alice holds an input $x$ (e.g. her password), and Bob holds an input $y$ (e.g. the password an honest Alice should possess), and they want to obtain the value of some function $f(x,y)$ (e.g. the equality function). Security means that the legitimate users should not learn anything beyond this specification. That is, Alice should not learn anything about $y$ and Bob should not learn anything about $x$, other than what they may be able to infer from the value of $f(x,y)$. We show that any such problem can be solved securely in the noisy-storage model by constructing protocols for bit commitment and oblivious transfer, where we prove security against the most general attack. Our protocols can be implemented with present-day hardware used for quantum key distribution. In particular, no quantum storage is required for the honest parties. Our work raises a large number of immediate theoretical as well as experimental questions related to many aspects of quantum information science, such as for example understanding the information carrying properties of quantum channels and memories, randomness extraction, min-entropy sampling, as well as constructing small handheld devices which are suitable for the task of secure identification. \\[4pt] Full version available at arXiv:0906.1030 (theoretical) and arXiv:0911.2302 (practically oriented). [Preview Abstract] |
Follow Us |
Engage
Become an APS Member |
My APS
Renew Membership |
Information for |
About APSThe American Physical Society (APS) is a non-profit membership organization working to advance the knowledge of physics. |
© 2018 American Physical Society
| All rights reserved | Terms of Use
| Contact Us
Headquarters
1 Physics Ellipse, College Park, MD 20740-3844
(301) 209-3200
Editorial Office
1 Research Road, Ridge, NY 11961-2701
(631) 591-4000
Office of Public Affairs
529 14th St NW, Suite 1050, Washington, D.C. 20045-2001
(202) 662-8700