The quantum search algorithm can be looked at as a technique for synthesizing a particular kind of superposition-one whose amplitude is concentrated in a single basis state. This basis state is defined by a binary function f(&xmacr;) that is nonzero in this desired basis state and zero everywhere else. This paper extends the quantum search algorithm to an algorithm that can create an arbitrarily specified superposition on a space of size N in O(sqrt[N] ) steps. The superposition is specified by a complex valued function f(&xmacr;) that specifies the desired amplitude of the system in basis state &xmacr;.
The quantum search algorithm can be looked at as a technique for synthesizing a particular kind of superposition-one whose amplitude is concentrated in a single basis state. This basis state is defined by a binary function f(&xmacr;) that is nonzero in this desired basis state and zero everywhere else. This paper extends the quantum search algorithm to an algorithm that can create an arbitrarily specified superposition on a space of size N in O(sqrt[N] ) steps. The superposition is specified by a complex valued function f(&xmacr;) that specifies the desired amplitude of the system in basis state &xmacr;.
Quantum computers and their algorithm are now widely studied.We consider the prob- lem of making a superposition with an arbitrarily specified amplitudes.By modifying Grover's quantum search algorithm, we show that this can be done in time O(N) with two simple operations, one is the Walsh-Hadamard transformation of $N\cross N$ -matrices where N=2n , the other is phase rotation of a state.If we see this problem in the classical computation model, it corresponds to the problem of making a sample with an arbitrarily specified distribution, where its time complexity is Ω(N) .By making a measurement on the result of our algorithm, it is possible to obtain a sample according to an arbitrarily specified probability distribution in O(N) time.
Quantum computation established itself as a promising emerging technology and, hence, attracted considerable attention in the domain of computer-aided-design (CAD). However, quantum mechanical phenomena such as superposition, phase shifts, or entanglement lead to a logic model which poses serious challenges to the development of a proper design flow for quantum circuits. Consequently, researchers addressed synthesis of quantum circuits not as a single design step, but considered sub-tasks such as synthesis of Boolean components or synthesis of restricted subsets of quantum functionality. Generating a particularly desired quantum state is another of these sub-tasks. However, logic synthesis of quantum circuits accomplishing that has hardly been considered yet. In this work, we propose a generic method which automatically synthesizes a quantum circuit generating any desired quantum state from an initially given basis state. The proposed method allows for both, a theoretical determination of upper bounds as well as an experimental evaluation of the number of quantum gates needed for this important design step.
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.
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 applications - an algorithm is presented that can create an arbitrarily specified quantum superposition on a space of size N in O(sqrt(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(sqrt(N)) steps. A classical algorithm would need O(N) steps.
IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.
Future quantum information processing devices will require the use of exotic quantum states, such as specially crafted entangled states, to achieve certain desired computations on demand. Thus far, synthesis schemes for such states have been devised on a case-by-case basis using ad hoc techniques. In this paper we present a systematic method for finding a quantum circuit that can synthesize any pure or mixed n-qubit state. We then give examples of the use of our algorithm for finding synthesis pathways for especially exotic quantum states such as maximal mixed states. It is not known how to prepare general instances of such states by other means. Thus our quantum state synthesis algorithm should be of use not only in quantum information processing, but also in experimental quantum physics.