We consider the partial database search problem where given a quantum database f : {0,1}n→{0,1} such that f(x) =1 for a unique x ∈ {0,1}n, we are required to determine only the first k bits of the address x. We present an algorithm and derive a lower bound for this problem. Let q(k,n) be the minimum number of queries needed to find the first k bits of the required address x with certainty (or with very high probability, say 1--O(N--¼)). We show that there exist constants ck (corresponding to the algorithm) and dk (corresponding to the lower bound) such that πover4 (1--dkover√K) √N ≤ q(k,n) ≤ πover4 (1--ckover√K) √N, where K=2k and N=2n. Our algorithm returns the correct answer with probability 1--O(N--½), and can be easily modified to give the correct answer with certainty. The lower bound for algorithms that return the correct answer with certainty is proved by reducing the usual database search problem to this partial search problem, and invoking Zalka's lower bound showing that Grovers algorithm is optimal for the usual database search problem. We then derive a lower bound that is applicable for database search algorithms that err with small probability, and use it to show that our lower bound also applies to partial search algorithms that return the correct answer with probability at least 1--O(N--¼).

This paper extends the quantum search class of algorithms to the multiple solution case.It is shown that, like the basic search algorithm, these too can be represented as a rotation in an appropriately defined two dimensional vector space.This yields new applicationsan algorithm is presented that can create an arbitrarily specified quantum superposition on a space of size N in o(4r-N) steps.By making a measurement on this superposition, it is possible to obtain a sample according to an arbitrarily specified classical probability distribution in O(,f-N) steps.A classical algorithm would need f2(N) steps.

It has recently been shown that the searching speed of computers based on quantum mechanics is far superior to their classical counterparts.

A framework is presented for the design and analysis of quantum mechanical algorithms, the 0( fi) step quantum search algorithm is an immediate consequence of this framework.It leads to several other search-type applications -an example is presented where the Walsh-Hadamard (W-H) transform of the quantum search algorithm is replaced by another transform tailored to the parameters of the problem.Also, it leads to quantum mechanical algorithms for problems not immediately connected with search -two such algorithms are presented for calculating the mean and median of statistical distributions.In order to classically estimate either the mean or median of a given distribution to a precision E , needs a(~-~) steps.The best known quantum mechanical algorithm for estimating the median takes O(E-') steps, and that for estimating the mean takes O(E -1.5 ) steps.This paper presents O(E-l) step algorithms for both problems (all bounds are upto polylogarithmic factors).Both algorithms are considerably simpler than known algorithms.

An unsorted database contains N records, of which just one satisfies a particular property.The problem is to identify that one record.Any classical algorithm, deterministic or probabilistic, will clearly take O (N) steps since on the average it will have to examine a large fraction of the N records.Quantum mechanical systems can do several operations simultaneously due to their wave like properties.This paper gives an O ( JN) step quantum mechanical algorithm for identifying that record.It is within a constant factor of the fastest possible quantum mechanical algorithm.

Simulated annealing is a powerful optimization technique based on the annealing phenomenon in crystallization. In this paper we propose a simulated sintering technique which is analogous to the sintering process in material processing. In sintering one improves the quality of a processed material by heating it to a temperature close to the melting point. Analogously, we show that by starting out with a good initial configuration instead of a random configuration, and restricting uphill moves, we can considerably speed up simulated annealing. We use this idea for a standard cell placement program - GRIM in LTX2, an AT&T Bell Labs VLSI layout system. The initial configuration is produced either by changes to a layout the designer had done previously, or else by a fast program like min-cut. We obtain improvements of about 10% in chip area starting from a min-cut placement, in times about 3 times faster than our simulated annealing program (which itself is several times faster than other well known simulated annealing programs).