TAILIEUCHUNG - A fast quantum mechanical algorithm for database search

One of several current trends in distributed database system de- sign is a move away from supporting traditional ACID database transactions. Some systems, such as Amazon’s Dynamo [13],Mon- goDB [24], CouchDB [6], and Cassandra [17] provide no transac- tional support whatsoever. Others provide only limited transaction- ality, such as single-row transactional updates (. Bigtable [11]) or transactions whose accesses are limited to small subsets of a database (. Azure [9], Megastore [7], and the Oracle NoSQL Database [26]). The primary reason that each of these systems does not support fully ACID transactions is to provide linear out- ward scalability. Other systems (. VoltDB [27, 16]) support full ACID, but cease (or. | A fast quantum mechanical algorithm for database search Lov K. Grover 3C-404A Bell Labs 600 Mountain Avenue Murray Hill NJ 07974 lkgrover@ Summary Imagine a phone directory containing N names arranged in completely random order. In order to find someone s phone number with a probability of 2 any classical algorithm whether deterministic or probabilis-N tic will need to look at a minimum of -2-- names. Quantum mechanical systems can be in a superposition of states and simultaneously examine multiple names. By properly adjusting the phases of various operations successful computations reinforce each other while others interfere randomly. As a result the desired phone number can be obtained in only O JN steps. The algorithm is within a small constant factor of the fastest possible quantum mechanical algorithm. 1. Introduction Background Quantum mechanical computers were proposed in the early 1980 s Benioff80 and in many respects shown to be at least as powerful as classical computers - an important but not surprising result since classical computers at the deepest level ultimately follow the laws of quantum mechanics. The description of quantum mechanical computers was formalized in the late 80 s and early 90 s Deutsch85 BB94 BV93 Yao93 and they were shown to be more powerful than classical computers on various specialized problems. In early 1994 Shor94 demonstrated that a quantum mechanical computer could efficiently solve a well-known problem for which there was no known efficient algorithm using classical computers. This is the problem of integer factorization . finding the factors of a given integer N in a time which is polynomial in logN. This is an updated version of a paper that originally appeared in Proceedings STOC 1996 Philadelphia PA uSa pages 212-219. This paper applies quantum computing to a mundane problem in information processing and presents an algorithm that is significantly faster than any classical algorithm can be. The problem

• Cơ sở dữ liệu
• especially costly
• generates competition
• among jurisdictions
• entrepreneurs and small
• environment conducive
• small businesses
• Ferraris
• apart and reassemble
• rainforest
• purported job
• creation role
• innovative prowess