This paper presents an enhancement to Grover's search algorithm for instances where the number of items (or the size of the search problem)
N is not a power of 2. By employing an efficient algorithm for the preparation of uniform quantum superposition states over a subset of the computational basis states, we demonstrate that a considerable reduction in the number of oracle calls (and Grover's iterations) can be achieved in many cases. For special cases (i.e., when
N is of the form such that it is slightly greater than an integer power of 2), the reduction in the number of oracle calls (and Grover's iterations) asymptotically approaches 29.33\%. This improvement is significant compared to the traditional Grover's algorithm, which handles such cases by rounding
N up to the nearest power of 2. The key to this improvement is our algorithm for the preparation of uniform quantum superposition states over a subset of the computational basis states, which requires gate complexity and circuit depth of only $ O (\log_2 (N)) $, without using any ancilla qubits.
Abstract Preparing quantum superposition states is a crucial step in realizing quantum algorithms, which demands substantial resources. In this paper, we propose a new method for preparing quantum uniform superposition states via quantum measurement, and design the bitwise implementation circuit, which only contains Hadamard, CNOT, and π /8 phase gates. Compared to the Shukla–Vedula method, the number of quantum gates required by both methods scales the same, while, the new method offers stronger fault tolerance, and the ancillary qubits employed during the implementation process can be reused, making it more suitable for implementation on real quantum computers. As an application, we provide the circuit for Shor’s discrete logarithm quantum algorithm, based on the new method, demonstrating its technical advantage for implementation of quantum algorithms.
Leveraging fundamental quantum features such as quantum superposition is one of the key elements for the theoretical speed-up obtained in quantum algorithms, e.g., with Grover's search algorithm. In this work, we explore the novel concept of dynamic state preparation, which allows for extending an initially prepared superposition state already containing a set of data elements. This state is modified upon receiving further time-series measurement data from an experiment so that this data can be processed with a quantum algorithm to extract the global properties of the system efficiently. Specifically, we distinguish the algorithmic case in which the state-preparation unitary of the initially prepared state to be extended is known and the one where it is not. The former can be described as an application of amplitude amplification, whereas the latter includes an amplitude reservoir assigned to a reference state that allows for extension without knowing the full state preparation unitary. We discuss both cases algorithmically and present the respective quantum circuit, including a specific initial state preparation method. Our analysis reveals a polynomial scaling and respective tradeoffs to be considered.