Added to Favorites

Related Searches

Definitions

Nearby Words

Cleveland, Grover (Stephen Grover Cleveland), 1837-1908, 22d (1885-89) and 24th (1893-97) President of the United States, b. Caldwell, N.J.; son of a Presbyterian clergyman. Cleveland's independence and conscientiousness in office marked him as a man of courage and personal integrity.## Early Career

## Presidency

**First Term****Second Term**## Bibliography

A lawyer in Buffalo, N.Y., he became (1882) the "veto mayor" who drove corruption from the city administration. He won the attention of Daniel Manning and the reform Democrats and was elected governor of New York. Cleveland further built his reputation as an enemy of machine politics by breaking violently with the Tammany leader, John Kelly, and supporting the bills prepared by Theodore Roosevelt to improve the government of New York City.

By 1884 he was a national figure, and he was nominated as Democratic "clean-government" candidate for President to oppose James G. Blaine. Cleveland, hated by Tammany and favored by political reformers, got the votes of many reform Republicans—the "mugwumps," who voted against their party. The campaign was notably bitter and was marked by the "Rum, Romanism, and Rebellion" speech of a Blaine supporter, which deeply offended Roman Catholics and may have swung the vote to Cleveland in the key state of New York.

Cleveland as President continued his independent and conscientious but conservative course. He did not go far enough in civil service reform to satisfy the zealots, but at the same time by keeping Republican government employees who were not "offensive partisans" he offended the Democratic spoilsmen. Cleveland was continually at odds with the Republican-controlled Senate.

The surplus revenue accumulating in the treasury largely because high Civil War tariffs were still in force fostered much "pork barrel" legislation. Cleveland vetoed such laws and argued for a lower tariff, devoting the whole of his annual message to Congress in 1887 to the question. The tariff was a major issue in the 1888 election. Cleveland received a popular majority but lost the electoral majority to his Republican opponent, Benjamin Harrison. A romantic note in his first administration was his marriage (1886) in the White House to his former ward, Frances Folsom.

In 1889 he retired to private life as a New York City lawyer, but opposition to measures of the Republican administration, notably the McKinley Tariff Act of 1890, brought him a new following. In 1892 he was again elected President. The Panic of 1893 struck a hard blow at his administration. Though the more radical Democrats saw salvation in free coinage of silver, the independent President sought to improve the economic situation by securing repeal of the Sherman Silver Purchase Act with the help of conservative Republicans.

Cleveland still urged lower tariffs, although the best opportunity had passed, since the treasury now had a deficit rather than a surplus. The Wilson Bill, embodying Cleveland's tariff ideas, passed the House of Representatives but was so altered by Senator A. P. Gorman and other protectionist Democrats that Cleveland, in disgust, refused to sign it. The rift between the President and the radical Democrats widened, especially over the gold standard, which Cleveland upheld. In the Pullman strike in 1894, Cleveland, on the grounds that the movement of U.S. mail was being halted by the strikers under Eugene V. Debs, sent troops into the area over the protest of Gov. J. P. Altgeld of Illinois. The strike was broken by the use of federal injunctions and the arrest of the strike leaders.

In foreign affairs both of Cleveland's administrations were marked by a strong stand on the Venezuela Boundary Dispute, which called forth a statement greatly enlarging the scope of the Monroe Doctrine. He refused to recognize the government set up in Hawaii by a revolution that was engineered by Americans who expected speedy annexation to the United States (although he recognized the republic in 1894), and he tried to discourage support of the revolutionists in Cuba. The more radical wing of the Democrats—the Silver Democrats—got control of the party in 1896 and nominated William Jennings Bryan, repudiating Cleveland. His strong second term had put him at odds with many (he was nicknamed the Great Obstructionist), and his *Presidential Problems* (1904) was mainly a defense of his own attitude on some of the major issues.

See R. E. Welch, Jr., *The Presidencies of Grover Cleveland* (1988); biographies by R. McElroy (1923), A. Nevins (1932), H. S. Merrill (1957), R. G. Tugwell (1968), and A. Brodsky (2000).

The Columbia Electronic Encyclopedia Copyright © 2004.

Licensed from Columbia University Press

Licensed from Columbia University Press

Grover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O(N^{1/2}) time and using O(logN) storage space (see big O notation). It was invented by Lov Grover in 1996.## Applications

## Setup

Consider an unsorted database with N entries. The algorithm requires an N-dimensional state space H, which can be supplied by log_{2}N qubits.^{n}, n is number of qubits in blank (zero) state.
## Algorithm steps

## Extensions

## Optimality

## References

## Notes

Classically, searching an unsorted database requires a linear search, which is O(N) in time. Grover's algorithm, which takes O(N^{1/2}) time, is the fastest possible quantum algorithm for searching an unsorted database. It provides "only" a quadratic speedup, unlike other quantum algorithms, which may provide exponential speedup over their classical counterparts. However, even quadratic speedup is considerable when N is large.

Like many quantum computer algorithms, Grover's algorithm is probabilistic in the sense that it gives the correct answer with high probability. The probability of failure can be decreased by repeating the algorithm. (An example of a deterministic quantum algorithm is the Deutsch-Jozsa algorithm, which always produces the correct answer with probability one.)

Although the purpose of Grover's algorithm is usually described as "searching a database", it may be more accurate to describe it as "inverting a function". Roughly speaking, if we have a function y=f(x) that can be evaluated on a quantum computer, this algorithm allows us to calculate x when given y. Inverting a function is related to the searching of a database because we could come up with a function that produces a particular value of y if x matches a desired entry in a database, and another value of y for other values of x.

Grover's algorithm can also be used for estimating the mean and median of a set of numbers, and for solving the Collision problem. In addition, it can be used to solve NP-complete problems by performing exhaustive searches over the set of possible solutions. This would result in a considerable speed-up over classical solutions, even though it does not provide the "holy grail" of a polynomial-time solution.

Below, we present the basic form of Grover's algorithm, which searches for a single matching entry. The algorithm can be further optimized if there is more than one matching entry and the number of matches is known beforehand.

Let us number the database entries by 1, 2,... , N. Choose an observable, Ω, acting on H, with N distinct eigenvalues whose values are all known. Each of the eigenstates of Ω encode one of the entries in the database, in a manner that we will describe. Denote the eigenstates (using bra-ket notation) as

- $\{|1rang,\; |2rang,\; cdots,\; |Nrang\}$

and the corresponding eigenvalues by

- $\{lambda\_1,\; lambda\_2,\; cdots,\; lambda\_\{N\}\; \}$

We are provided with a unitary operator, U_{ω}, which acts as a subroutine that compares database entries according to some search criterion. The algorithm does not specify how this subroutine works, but it must be a quantum subroutine that works with superpositions of states. Furthermore, it must act specially on one of the eigenstates, |ω>, which corresponds to the database entry matching the search criterion. To be precise, we require U_{ω} to have the following effects:

- $U\_omega\; |omegarang\; =\; -\; |omegarang$

- $U\_omega\; |xrang\; =\; |xrang\; qquad\; mbox\{for\; all\}\; x\; ne\; omega$

- $langle\; omega|\; omegarang\; =1$.

- $langle\; omega|\; x\; rang\; =langle\; x|\; omegarang\; =0$.

- $U\_omega\; |omegarang\; =\; (I-2|\; omegarangle\; langle\; omega|)|omegarang=|omegarang-2|\; omegarangle\; langle\; omega|omegarang=-|omegarangle$.

- $U\_omega\; |xrang\; =\; (I-2|\; omegarangle\; langle\; omega|)|xrang=|xrang-2|\; omegarangle\; langle\; omega|xrang=|xrangle$.

Our goal is to identify this eigenstate |ω>, or equivalently the eigenvalue ω, that U_{ω} acts specially upon.

Also we can write:

- $langomega|srang\; =lang\; s|omegarang\; =\; frac\{1\}\{sqrt\{N\}\}$.

- $langle\; s|\; srang\; =Nfrac\{1\}\{sqrt\{N\}\}cdot\; frac\{1\}\{sqrt\{N\}\}=1$.

- $U\_omega\; |srang\; =\; (I-2|\; omegarangle\; langle\; omega|)|srang=|srang-2|\; omegarangle\; langle\; omega|srang=|srang-frac\{2\}\{sqrt\{N\}\}|omegarangle$.

- $U\_s(|srang-frac\{2\}\{sqrt\{N\}\}|omegarangle)\; =\; (2\; |srang\; lang\; s|\; -\; I)(|srang-frac\{2\}\{sqrt\{N\}\}|omegarangle)=2\; |srang\; lang\; s|srang-|srang-frac\{4\}\{sqrt\{N\}\}|srang\; langle\; s|omegarang+frac\{2\}\{sqrt\{N\}\}|omegarang=$.

- $=2|srang-|srang-frac\{4\}\{sqrt\{N\}\}cdotfrac\{1\}\{sqrt\{N\}\}|srang+frac\{2\}\{sqrt\{N\}\}|omegarang=|srang-frac\{4\}\{N\}|srang+frac\{2\}\{sqrt\{N\}\}|omegarang=frac\{N-4\}\{N\}|srang+frac\{2\}\{sqrt\{N\}\}|omegarang$.

The steps of Grover's algorithm are as follows:

- Initialize the system to the state
- $|srang\; =\; frac\{1\}\{sqrt\{N\}\}\; sum\_\{x=1\}^\{N\}\; |xrang$

- Perform the following "Grover iteration" r(N) times. The function r(N) is described below.
- Apply the operator $U\_omega=I-2|\; omegarangle\; langle\; omega|$.
- Apply the operator $U\_s\; =\; 2\; left|srightrangle\; leftlangle\; sright|\; -\; I$.

- Perform the measurement Ω. The measurement result will be λ
_{ω}with probability approaching 1 for N>>1. From λ_{ω}, ω may be obtained.

Our initial state is

- $|srang\; =\; frac\{1\}\{sqrt\{N\}\}\; sum\_\{x=1\}^\{N\}\; |xrang$

Consider the plane spanned by |s> and |ω>. Let |ω^{×}> be a ket in this plane perpendicular to |ω>. Since |ω> is one of the basis vectors, the overlap is

- $langomega|srang\; =lang\; s|omegarang\; =\; frac\{1\}\{sqrt\{N\}\}$

In geometric terms, there is an angle (π/2 - θ/2) between |ω> and |s>, where θ/2 is given by:

- $cos\; left(frac\{pi\}\{2\}\; -\; frac\{theta\}\{2\}\; right)\; =\; frac\{1\}\{sqrt\{N\}\}$

- $sin\; frac\{theta\}\{2\}\; =\; frac\{1\}\{sqrt\{N\}\}$

The operator U_{ω} is a reflection at the hyperplane orthogonal to |ω>; for vectors in the plane spanned by |s> and |ω>, it acts as a reflection at the line through |ω^{×}>. The operator U_{s} is a reflection at the line through |s>. Therefore, the state vector remains in the plane spanned by |s> and |ω> after each application of U_{s} and after each application of U_{ω}, and it is straightforward to check that the operator U_{s}U_{ω} of each Grover iteration step rotates the state vector by an angle of θ toward |ω>.

We need to stop when the state vector passes close to |ω>; after this, subsequent iterations rotate the state vector away from |ω>, reducing the probability of obtaining the correct answer. The number of times to iterate is given by r:

- $r\; rightarrow\; frac\{pi\; sqrt\{N\}\}\{4\}$

The probability of measuring the correct answer is:

- $sin^2left(frac\{2r+1\}\{2\}\; thetaright)\; ,$

- $theta\; =\; 2arccosleft(sqrt\{1-frac\{1\}\{N\}\}\; right)=2arcsin\; frac\{1\}\{sqrt\{2^n\}\}\; .$

If, instead of 1 matching entry, there are k matching entries, the same algorithm works but the number of iterations must be π(N/k)^{1/2}/4 instead of πN^{1/2}/4.
There are several ways to handle the case if k is unknown. For example, one could run Grover's algorithm several times, with

- $pi\; frac\{N^\{1/2\}\}\{4\},\; pi\; frac\{(N/2)^\{1/2\}\}\{4\},$

iterations. For any k, one of iterations will find a matching entry with a sufficiently high probability. The total number of iterations is at most

- $pi\; frac\{N^\{1/2\}\}\{4\}\; left(1+\; frac\{1\}\{sqrt\{2\}\}+frac\{1\}\{2\}+cdotsright)$

which is still O(N^{1/2}).

It is known that Grover's algorithm is optimal. That is, any algorithm that accesses the database only by using the operator U_{ω} must apply U_{ω} at least as many times as Grover's algorithm. This result is important in understanding the limits of quantum computation.
If the Grover's search problem was solvable with log^{c} N applications of U_{ω}, that would imply that NP is contained in BQP, by transforming problems in NP into Grover-type search problems. The optimality of
Grover's algorithm suggests (but does not prove) that NP is not contained in BQP.

The number of iterations for k matching entries, π(N/k)^{1/2}/4, is also optimal.

- Grover L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
- Grover L.K.: From Schrödinger's equation to quantum search algorithm, American Journal of Physics, 69(7): 769-777, 2001. Pedagogical review of the algorithm and its history.
- http://www.bell-labs.com/user/feature/archives/lkgrover/
- http://arxiv.org/abs/quant-ph/0301079 Grover's Algorithm: Quantum Database Search
- Grover's algorithm on arxiv.org

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday August 20, 2008 at 04:26:53 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Wednesday August 20, 2008 at 04:26:53 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.