<p>Finding the minimum value in a large unstructured database is a common and fundamental task in computer science with broad applications across science and industry. However, the optimal classical deterministic algorithm can find the minimum value with a time complexity that grows linearly with the number of elements in the database. In this paper, we present the proposal of a quantum algorithm for finding the minimum value of a database, which is quadratically faster than its best classical analogs. We assume a quantum random access memory (QRAM) that stores values from a database and performs an iterative search based on an oracle whose role is to limit the searched values by controlling the states of the most significant qubits. We provide a detailed description of the quantum circuit implementation, analyze its complexity, and demonstrate a significant computational advantage, particularly for large-scale datasets. In addition, a complexity analysis was performed in order to demonstrate the advantage of this quantum algorithm over its classical counterparts. Thus, the presented quantum minimum search (QMS) algorithm represents a promising tool for practical computing scenarios, offering a robust foundation for further research into fault-tolerant quantum algorithms.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Quantum Algorithm for Finding Minimum Values in a Quantum Random Access Memory

  • Anton S. Albino,
  • Lucas Q. Galvão,
  • Mauro Q. Nooblath Neto,
  • Ethan Hansen,
  • Clebson Cruz

摘要

Finding the minimum value in a large unstructured database is a common and fundamental task in computer science with broad applications across science and industry. However, the optimal classical deterministic algorithm can find the minimum value with a time complexity that grows linearly with the number of elements in the database. In this paper, we present the proposal of a quantum algorithm for finding the minimum value of a database, which is quadratically faster than its best classical analogs. We assume a quantum random access memory (QRAM) that stores values from a database and performs an iterative search based on an oracle whose role is to limit the searched values by controlling the states of the most significant qubits. We provide a detailed description of the quantum circuit implementation, analyze its complexity, and demonstrate a significant computational advantage, particularly for large-scale datasets. In addition, a complexity analysis was performed in order to demonstrate the advantage of this quantum algorithm over its classical counterparts. Thus, the presented quantum minimum search (QMS) algorithm represents a promising tool for practical computing scenarios, offering a robust foundation for further research into fault-tolerant quantum algorithms.