Bulletin of the American Physical Society
APS March Meeting 2010
Volume 55, Number 2
Monday–Friday, March 15–19, 2010; Portland, Oregon
Session A26: Focus Session: Recent Progress in Quantum Algorithms and Computational Complexity
8:00 AM–10:48 AM,
Monday, March 15, 2010
Sponsoring Unit: GQI
Chair: Dave Bacon, University of Washington
Abstract ID: BAPS.2010.MAR.A26.12
Abstract: A26.00012 : Performance evaluation of a classical database search that internally simulates an ensemble quantum database search*
10:36 AM–10:48 AM
Preview Abstract Abstract
(Research Center for Quantum Computing, Interdisciplinary Graduate School of Science and Engineering, Kinki University, Japan)
Average computation time of classical database search for non-trivial oracles, such as one for SAT, is known to exhibit a certain dependence on the constraint density of instances. We investigate this property for a solver that internally uses a matrix-product-state (MPS) simulation of an extended Bruschweiler search. The database search tool that we had used in [A. SaiToh and M. Kitagawa, Phys. Rev. A 73, 062332 (2006)] has been extended in precision and improved in the speed. This enabled us to evaluate the tool for a larger size of inputs. It is found that the dependence on the constraint density for our tool is different from those for the conventional solvers; this suggests that the MPS approach is useful as a complementary method. Results are shown for several non-trivial conjunctive and disjunctive normal forms.
*Supported by the ``Open Research Center" Project for Private Universities: matching fund subsidy from MEXT, and Grant-in-Aid for Scientific Research from JSPS (Grant No. 21800077).
To cite this abstract, use the following reference: http://meetings.aps.org/link/BAPS.2010.MAR.A26.12
The American Physical Society (APS) is a non-profit membership organization working to advance the knowledge of physics.
1 Physics Ellipse, College Park, MD 20740-3844
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