Bulletin of the American Physical Society
APS March Meeting 2015
Volume 60, Number 1
Monday–Friday, March 2–6, 2015; San Antonio, Texas
Session A18: Invited Session: Recent Advances in Quantum Algorithms |
Hide Abstracts |
Sponsoring Units: GQI DAMOP Chair: Nathan Wiebe, Microsoft Research Room: Mission Room 103A |
Monday, March 2, 2015 8:00AM - 8:36AM |
A18.00001: Nonlinear (quantum) search Invited Speaker: David Meyer Farhi and Gutmann's ``analog analogue'' of Grover's algorithm is simply the Schr\"odinger equation for the evolution of a particle hopping among $N$ sites, one of which is marked by the presence of a potential well. When the particle is initialized in a state with equal amplitude at each site, after $O(N^{1/2})$ time its amplitude is concentrated at the marked site, and a measurement will detect it there with probability 1. A nonlinear Schr\"odinger equation with a cubic nonlinear term arises as the Gross-Pitaevskii equation approximately describing the collective evolution of the many quantum particles in a Bose-Einstein condensate (BEC), a novel---but experimentally observed---form of matter in which all the particles are in the same quantum state. Including such a nonlinear term into the continuous time evolution of the particle hopping among $N$ sites, one of which is marked, constitutes a nonlinear (quantum) search algorithm. If the relative strength of the nonlinear term varies correctly with time, the state concentrates at the marked site at time $\pi/2$ for {\sl any\/} $N$. This is a {\sl constant time\/} algorithm---immensely faster than $O(N^{1/2})$. The state concentrates at the marked site for shorter and shorter times as $N\to\infty$, however, which means the measurement time must be determined with increasing precision. Accounting correctly for the physical resources necessary to measure time sufficiently precisely, the total resources for this algorithm scale as $O(N^{1/2})$, no better than Farhi and Gutmann's linear quantum algorithm. But jointly optimizing these resource requirements results in an overall scaling of $N^{1/4}$. This is a significant, but not unreasonable, improvement over the $N^{1/2}$ scaling of the linear algorithm. Since the Gross-Pitaevskii equation approximates the multi-particle (linear) Schr\"odinger equation, for which Grover's algorithm is optimal, this gives a quantum information-theoretic lower bound on the number of particles needed for the approximation to hold, asymptotically. This is joint work with Tom Wong. [Preview Abstract] |
Monday, March 2, 2015 8:36AM - 9:12AM |
A18.00002: Quantum algorithms for quantum field theories Invited Speaker: Stephen Jordan Ever since Feynman's original proposal for quantum computers, one of the primary applications envisioned has been efficient simulation of other quantum systems. In fact, it has been conjectured that quantum computers would be universal simulators, which can simulate all physical systems using computational resources that scale polynomially with the system's number of degrees of freedom. Quantum field theories have posed a challenge in that the set of degrees of freedom is formally infinite. We show how quantum computers, if built, could nevertheless efficiently simulate certain quantum field theories at bounded energy scales. Our algorithm includes a new state preparation technique which we believe may find additional applications in quantum algorithms. [Preview Abstract] |
Monday, March 2, 2015 9:12AM - 9:48AM |
A18.00003: Boson Sampling for Molecular Vibronic Spectra Invited Speaker: Gian Giacomo Guerreschi Quantum computers are expected to be more efficient in performing certain computations than any classical machine. Unfortunately, the technological challenges associated with building a fullscale quantum computer have not yet allowed the experimental verification of such an expectation. Recently, boson sampling has emerged as a problem that is suspected to be intractable on any classical computer, but efficiently implementable with a linear quantum optical setup. Therefore, boson sampling may o er an experimentally realizable challenge to the Extended Church-Turing thesis and this remarkable possibility motivated much of the interest around boson sampling, at least in relation to complexity-theoretic questions. In this work, we show that the successful development of a boson sampling apparatus would not only answer such inquiries, but also yield a practical tool for difficult molecular computations. Specifically, we show that a boson sampling device with a modified input state can be used to generate molecular vibronic spectra, including complicated effects such as Duschinsky rotations. [Preview Abstract] |
Monday, March 2, 2015 9:48AM - 10:24AM |
A18.00004: ABSTRACT WITHDRAWN |
Monday, March 2, 2015 10:24AM - 11:00AM |
A18.00005: Hidden subgroups and hidden polynomials Invited Speaker: Miklos Santha Efficient solutions for the abelian hidden subgroup problem (HSP) constitute probably the greatest success of quantum computing. As a sequel to these results, various generalizations of the abelian HSP have been investigated, such as the non abelian HSP, hidden symmetry problems, and hidden structures of higher degree. In this talk we review an interesting connection between the HSP in certain semidirect product p-groups of constant nilpotency class and the multi-dimensional univariate hidden polynomial graph problem when the degree of the polynomials is constant. Using that connection, we present an efficient quantum solution for both, based on a new randomized algorithm for solving systems of diagonal polynomial equations in finite fields. \\[4pt] Joint work with G\'abor Ivanyos. [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. |
© 2024 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
100 Motor Pkwy, Suite 110, Hauppauge, NY 11788
(631) 591-4000
Office of Public Affairs
529 14th St NW, Suite 1050, Washington, D.C. 20045-2001
(202) 662-8700