Efficient quantum search algorithms on a bulk quantum computation model

Zijian Diao, Goong Chen

Y. Yamamoto, Cyrus P. Master

Quantum algorithms for problems such as integer factorization and database search have spurred great interest in quantum computation. However, the construction of scalable quantum computers has proved to be extremely difficult. Among the challenging requirements that must be fulfilled in the “standard model” of quantum computation, one must be able to initialize qubits into known pure states. In addition, quantum computers must be protected from noise due to unwanted interactions with their environment. This work is concerned with two theoretical issues motivated by these difficulties. First, I analyze the efficiency of an algorithm for an alternate model for quantum computation that is motivated by bulk nuclear magnetic resonance. In such ensemble systems, the initial state is not a fiducial pure state, but is instead a maximally-mixed density operator. The algorithm that I consider allows one to estimate the free energy of arbitrary spin-1/2 lattice models. To determine the efficiency of this algorithm, I calculate the computation time required to estimate the free energy to bounded error as a function of the lattice size. In the absence of stochastic fluctuations in the measurement output, it is found that the algorithm is efficient. However, evidence is presented that suggests that the algorithm becomes exponentially sensitive to fluctuations as the lattice size increases. While techniques such as quantum error-correcting codes and decoherence-free subsystem encodings have been devised to mitigate errors due to unwanted environmental couplings, these methods require many additional qubits or complicated encodings. Here, I investigate a simple approach to reduce errors in the quantum search algorithm due to a collective decoherence model. This method takes advantage of the freedom inherent in compiling the search algorithm into fundamental gates. Transition rate calculations and more rigorous quantum master equation simulations are carried out for small-qubit instances to contrast the performance of the original and modified algorithm. It is shown that the expected computational effort can be reduced by 22% for selected five-bit instances of the quantum search algorithm. While this approach does not constitute a general strategy for quantum error-correction, it illustrates the importance of judicious gate design in mitigating decoherence.

Jonathan A. Jones, Michele Mosca, Rasmus H. Hansen

P. Oscar Boykin, Tal Mor, Vwani Roychowdhury +1 more

In ensemble (or bulk) quantum computation, measurements of qubits in an individual computer cannot be performed. Instead, only expectation values can be measured. As a result of this limitation on the model of computation, various important algorithms cannot be processed directly on such computers, and must be modified. We provide modifications of various existing protocols, including algorithms for universal fault--tolerant computation, Shor's factorization algorithm (which can be extended to any algorithm computing an NP function), and some search algorithms to enable processing them on ensemble quantum computers.

이수준

Tamás Varga, László Bacsárdi

The efficient search in unsorted database is extremely important for our everydays' applications. This type of search is useful in communication networks as well, since routing can be considered as a search in the database of the routing table. From the viewpoint of quantum computing, the not quantum-based solutions are named as classical. The search could be very time-consuming and computationally task if we need to solve it using classical algorithms, particularly for large data sets. This process can be accelerated and be more efficient by the application of quantum search algorithms. To investigate the quantum search, we have developed a Java-based system to simulate different quantum algorithms which are based on elementary quantum gates. In our model, we took into account the computation errors of the elementary quantum gates. We analyzed how these errors affect the efficiency of quantum search.