Iterative Qubits Management for Quantum Search

Recent advances in quantum computing systems attract tremendous attention. Commercial companies, such as IBM, Amazon, and IonQ, have started to provide access to noisy intermediate-scale quantum computers. Researchers and entrepreneurs attempt to deploy their applications that aim to achieve a quantum speedup. Grover’s algorithm and quantum phase estimation are the foundations of many applications with the potential for such a speedup. While these algorithms, in theory, obtain marvelous performance, deploying them on existing quantum devices is a challenging task. For example, quantum phase estimation requires extra qubits and a large number of controlled operations, which are impractical due to low-qubit and noisy hardware. To fully utilize the limited onboard qubits, we develop a distributed application with a key-value data structure based on Grover’s algorithm called IQuCS . Consider a database with duplicates. By encoding each element to a binary type with a unique key and forming a key-value pair, we can count the number of occurrences of each element in the database based on quantum computing. We have optimized the operation process by filtering data points to make it more efficient. To determine the effect of this optimization, we evaluate it with datasets of different sizes and with different numbers of duplicates. With the assistance of classical computers, IQuCS can reduce the problem set for each query. Due to this reduction, IQuCS requires fewer qubits. Through the iterative management, IQuCS achieves a reduction of qubit virtualized consumption, up to 66.2%, with reasonable accuracy.