Abstract
The quantum search algorithm can be synthesized with almost any unitary operation, provided there is only a single solution. This paper extends the generalized quantum search algorithm to the situation with multiple solutions;
Abstract
this solves an open problem in quantum computing. It is shown that, like the basic generalized search algorithm, this too can be represented as a rotation in a two dimensional complex Hilbert space. This yields new applications -an algorithm is presented that can create an arbitrarily specified superposition on a space of size in steps. By making a measurement on this superposition, it is possible to obtain a sample according to an arbitrarily specified classical probability distribution in steps. A classical algorithm would need steps.
Introduction
(i) Sampling: Sampling is a fundamental technique for approximating answers that cannot be directly, or efficiently, computed. The uses of sampling for gathering information is the primary domain of the field of statistics. Some applications of sampling are: Monte Carlo integration [S5] , approximating the permanent [S2] and testing primality [S9] .
Introduction
Sampling has been linked to complexity theory by the work of Jerrum, Valiant and Vazirani [S7] who showed a link between counting and random generation. Sampling has also been used to estimate marginal densities in Bayesian inference [S4] and in statistical approaches to imaging and image restoration [S3] . For some applications uniform sampling is enough but for most applications one needs sampling according to a specified probability distribution. It is known how to rapidly generate samples when the probability distribution has certain properties. For example when the distribution is log concave, samples can be generated in logarithmic time [S1] . This leads to applications through which it is possible to rapidly estimate the volumes of convex structures and approximately integrate certain classes of functions [S1, S8] .
Introduction
In general, the probability distributions are only specified implicitly, i.e. it is possible to calculate the probability of any given point easily but there is no known structure to the distribution. A simple algorithm that can sample according to a specified probability distribution in steps is the following. Partition the points into two groups each of which has half of the points. Find the total probability of each group by summing the probabilities of each point in the group. Pick one of the two groups with these probabilities. Repeat the procedure on this group and keep repeating until there are only a few points in the final group and then pick one of the points with this probability.
Introduction
The number of steps required can be reduced to by keeping careful track of summations. However, it is not possible to sample precisely according to an arbitrary probability distribution in fewer than classical steps. For example, it is easily seen that we will need to examine at least half the points, for if we leave out half of the points we 1. This material is based upon work supported in part by the U. S. Army Research Office under contract no. DAAG55-98-C-0040.
Introduction
could be missing a point with an arbitrarily high probability, e.g. consider the situation where all the probability is localized in a single point.
Introduction
A quantum mechanical system is in multiple states simultaneously, quantum computing algorithms make use of this feature. This paper uses the generalized search scheme to develop a quantum algorithm that can create an arbitrarily specified superposition (and hence an arbitrary probability distribution) on points in steps.
Introduction
(ii) Quantum computing: Just as classical digital systems can be constructed out of two state systems called bits, quantum mechanical systems can be constructed out of basic two state quantum mechanical systems called qubits.
Introduction
Quantum mechanical operations that can be carried out in a controlled way are unitary operations that act on a small number of qubits in each step. A good starting point to think of quantum mechanical algorithms is probabilistic algorithms [Q2] (e.g. simulated annealing). In a quantum mechanical algorithm, the system is started in a state that is easy to prepare on which a sequence of simple operations is applied. When the system is observed after applying these operations, it gives the answer to a difficult computational problem with a high probability. Some examples of powerful quantum mechanical algorithms are [Q12] , [Q13] , [Q9] .
Introduction
Just like classical probabilistic algorithms, quantum mechanical algorithms work with a probability distribution over various states. However, unlike classical systems, the probability vector does not completely describe the system. In order to completely describe the system we need the amplitude in each state which is a complex number.
Introduction
The probabilities in any state are given by the square of the absolute values of the amplitude in that state. The evolution of the system is obtained by premultiplying this amplitude vector (that describes the distribution of amplitudes over various states) by a transition matrix, the entries of which are complex in general. It can be shown that in order to conserve probabilities, the state transition matrix has to be unitary, i.e. the columns of the transformation matrix are orthonormal [Q2] . It is easily shown that the following three transformations are unitary: NOT (a one-input one-output gate where the output is the inversion of the input), CNTRL-NOT (a two-input two-output gate where the first bit is unaffected and the second input is inverted if the first is 1) & CNTRL-CNTRL-NOT (a three-input three-output gate where the first two inputs are unaffected and the third is inverted if the first two qubits are both 1). These are the analogs of classical NAND and NOR gates. Using these three gates it is possible to synthesize any boolean function that can be synthesized classically with approximately the same number of gates. In order to develop more powerful quantum mechanical algorithms, we need some operations that are basically quantum mechanical. The two such operations that we will need are the W-H transformation operation and the selective inversion of the phase of certain states, these are discussed in the following two paragraphs.
Introduction
A basic operation in quantum computing is the operation M performed on a single qubit -this is represented by the following matrix: , i.e. the state 0 is transformed into a superposition where the two states & have the same amplitude of , this superposition is denoted by: ; similarly state 1 is transformed into
Introduction
A system consisting of n qubits has basis states. We can perform the transformation M on each qubit independently in sequence, thus transforming the state of the system. The state transition matrix representing this operation is of dimension . Consider a case when the starting state is one of the 2 n basis states, i.e. a state described by a general string of n binary digits composed of some 0s and some 1s. The result of performing the transformation M on each qubit will be a superposition of states consisting of all possible n bit binary strings with amplitude of each state being . This transformation is referred to as the W-H transformation [Q8] .
Introduction
The other transformation that we need is the selective phase inversion of the amplitude in certain states. The transformation matrix describing this for a 4 state system with selective phase inversion of the second state is:
Introduction
. Unlike the W-H transformation, the probability in each state stays the same. A realization of this kind of transformation can be achieved using the gates discussed so far [Q4] .
Introduction
In the quantum search algorithm, a function defined over states (denoted by ) is given which is known to be non-zero at a single value of , say (t for target) -the goal is to find . If there was no other information about and one were using a classical computer, then on the average it would take function evaluations to solve this problem successfully. [Q9] found a quantum mechanical algorithm that took only steps.
Introduction
The quantum search algorithm [Q9] Q5] ). This showed that one could use any starting state and unitary operation and from these amplify the amplitude in a desired target state t. A new class of algorithms was thus invented. These extended far beyond search problems -in fact, it was shown that this framework could be used to enhance almost any quantum mechanical algorithm [Q10] .
Introduction
One constraint with these algorithms was that they work when the problem has exactly one state. For many
Introduction
problems like game-tree search, this was a restriction and the algorithms either could not be shown to work with multiple solutions or needed complicated workarounds [Q6] . The paper [Q11] 2. This paper This paper shows how the basic generalized search algorithm can be extended to the multi-solution case. From this an algorithm for generating an arbitrarily specified superposition is deduced. This can be used to sample according to a general probability distribution -the number of steps required is approximately the square-root of that of the corresponding classical algorithm. The following is the organization of the rest of this paper:
Introduction
-section 3 carries out a general analysis of the generalized search algorithm, -section 4 considers the case with a single solution, -section 5 extends this to the multi-solution case, -section 6 shows how this can be used to generate an arbitrarily specified superposition.
Generalized search (general analysis)
The algorithm starts with the system in an s state (s for source), the object is to drive the system into the t states, note that there is a single s state but multiple t states. The following sections show how this can be accomplished by means of an operation Q which is defined as the composite operation (note that this denotes the sequence of operations: first U, then , then , and finally .)
Generalized search (general analysis)
is a diagonal matrix with all diagonal elements equal to 1 except the element which is . In Dirac notation, which is commonly used for matrix operations in quantum mechanics, may be written as . Here is the identity matrix and the column vector with all except the element equal to zero, the element is , denotes the corresponding row vector. Similarly is a diagonal matrix with all diagonal elements equal to except the elements which are equal to . can be written in the form , where is the column vector with all elements equal to , except a single one of the elements which is , is the corresponding row vector. U denotes an arbitrary unitary matrix and is its inverse. The following results hold for arbitrary , section 6 describes how to choose based on the specified probability distribution.
Generalized search (general analysis)
In this notation,
-

I s -

I s ss th

-
. Also, since is unitary, is equal to the transpose of the complex conjugate of , and therefore which is equal to . Therefore the above equation becomes:
-
Similarly, for any t state:
-
The analysis so far shows that, if there are t states, then the dimensional space defined by the vector and the vectors is preserved by the operator . The next two sections show that there is indeed a simpler two dimensional subspace that is also preserved.
Single solution case
First of all consider the situation with a single t state. This is the same as the generalized search situation considered previously [Q10] . In this section, we quickly rederive the main result since, in the next section, this will help to analyze the general case.
Single solution case
Thus is a transformation in the 2-dimensional vector space defined by the two vectors and . In matrix notation this may be written as the following transformation:
Single solution case
.
Single solution case
In order to find the effect of repeated applications of , we use standard matrix analysis which consists of is thus a transformation in the two dimensional complex Hilbert space defined by and . Normalizing the vector and denoting by , the above transformation can be represented as:
Single solution case
This is exactly the same transformation as in the previous section. Therefore, as in the previous section, if U ts
Single solution case
applications of transform the vector into . The case when is is very similar; however, this is not particularly interesting since this can be solved with a high probability by just applying to once and observing the state.
Single solution case
Note that the algorithm in the previous section was only shown to work when was real. The results of this section show that a very similar result holds in the single solution case, even when is complex.
State vector engineering
Suppose that we are required to synthesize a specified superposition. The amplitude in each of states, denoted by , is required to be proportional to a given function . Assume, without loss of generality, that the maximum value of is .
State vector engineering
The following algorithm synthesizes the specified superposition in approximately steps. One immediate application of this algorithm is in sampling according to an arbitrary probability distribution in steps. For this a quantum superposition is generated and then through a measurement in an appropriate basis, a sample is obtained.
Solution Define
states by qubits, denoted by . Include an additional ancilla qubit. Initialize the state so that all qubits are in the state -the state of the whole system is denoted by: (the first denotes a single qubit in the state and denotes each of the other qubits in the state.)
Solution Define
Next consider the following unitary operations (which constitute the building blocks for our algorithm):
Solution Define
: leave the first qubit unaltered and apply a W-H transform to the other qubits.
Solution Define
: carry out a conditional rotation of the first qubit so that the state: gets transformed into the following superposition: , i.e. the amplitude of the state is and the amplitude of the state is . This type of unitary operation has previously been used in quantum computing algorithms, e.g. [Q10] . It can be accomplished by first transferring into the phase through conditional phase inversion and then convert it into amplitude information.
Solution Define
: in case the first qubit is , invert the phase; if the first qubit is , leave it unchanged. In other words, states with the first qubit in the state are t states. 
Observations:
(i) Let be at points in the domain and zero everywhere else. Since , the algorithm needs steps. After this it reaches the same superposition as reached in the basic quantum search algorithm with solutions and it needs exactly the same number of steps as the quantum search algorithm to reach this.
Observations:
(ii) The number of steps required by the algorithm depends on . In case this quantity is not known in advance, the superposition can still be synthesized in steps, by trying out the algorithm with a few carefully chosen runtimes. After this the ancilla qubit is measured -the algorithm is repeated until this is observed to be (it can be shown that, with appropriately chosen runtimes, the probability of not getting even a single falls exponentially with the square of the number of times the procedure is repeated [Q7] ). Once a is observed, the remaining qubits immediately collapse into the desired superposition.
Observations:
(iii) The algorithm assumed that the function was normalized so that its maximum value was equal to . The algorithm as presented in this section is equally valid for different , provided the maximum value does not
Observations:
exceed . For example, if the desired probability at each is specified (i.e. ), the value of becomes and the algorithm needs exactly iterations to attain this distribution. In general, the number of steps required is smaller if we can choose a larger constant to scale . This is maximized for the choice made in this section where the maximum value of is .
Observations:
(iv) The analysis presented above is very similar for the situation where the initial state , instead of being a basis state is an arbitrary superposition as considered in [Q3] . The main difference is that in the computational basis, (the matrix that inverts the phase of the source state) will not be diagonal. Of course, it will be diagonal in any basis that includes . In terms of the Dirac notation it will still be described as , i.e. it reflects the state and leaves all orthogonal states unchanged.
Observations:
(v) A superposition with multiple target states, of the type discussed in section 5, is a pure state in a different basis.
Observations:
Thus the algorithm rotates from a given source state to another pure state. This is just like quantum search except that the final state is a basis state in a different basis -the quantum search algorithm as previously known would only rotate into a pure basis state in the same basis.
Conclusion
The quantum search algorithm is perhaps the simplest possible quantum mechanical algorithm that yields a significant advantage over a classical algorithm. It has inspired several new ideas and algorithms. This paper presents the most recent development which shows that the amplitude amplification class of algorithms can be made to work in the presence of multiple target states. One application of this has been presented where one can generate a sample according to an arbitrary probability distribution in a number of steps which is only a square-root of that required by a classical algorithm. Another immediate application is in extending the framework of the generalized search class of algorithms of the type discussed in [Q5] & [Q10] , so that they are no longer limited to problems with a single solution.
Acknowledgements
Thanks to Ashwin Nayak, Norm Margolus, Hein Roehrig and Charles Bennett for going through the paper and making valuable comments.
References
Sampling related references:
References
[S1] D. Applegate & S. Kannan, Sampling and integration of log-concave functions, Proceedings of the 23rd
References
Annual ACM Symposium on Theory of Computing (STOC), 1991, 156-163. [S2] A. Broder, How hard is to marry at random? (On the approximation of the permanent), Proc. 18th ACM

{'paper_id': '14474653', 'title': 'Rapid sampling through quantum computing 1', 's2_url': 'https://api.semanticscholar.org/CorpusID:14474653', 'source': 'S2ORC'}