Modelling of Grover's quantum search algorithms: implementations of simple quantum simulators on classical computers

Автор: Ulyanov Sergey, Reshetnikov Andrey, Tyatyushkina Olga

Журнал: Сетевое научное издание «Системный анализ в науке и образовании» @journal-sanse

Статья в выпуске: 3, 2020 года.

Бесплатный доступ

Models of Grover’s search algorithm is reviewed to build the foundation for the other algorithms. Thereafter, some preliminary modifications of the original algorithms by others are stated, that increases the applicability of the search procedure. A general quantum computation on an isolated system can be represented by a unitary matrix. In order to execute such a computation on a quantum computer, it is common to decompose the unitary into a quantum circuit, i.e., a sequence of quantum gates that can be physically implemented on a given architecture. There are different universal gate sets for quantum computation. Here we choose the universal gate set consisting of CNOT and single-qubit gates. We measure the cost of a circuit by the number of CNOT gates as they are usually more difﬁcult to implement than single qubit gates and since the number of single-qubit gates is bounded by about twice the number of CNOT’s.

Еще

Quantum computation, grover's search algorithm, quantum search algorithm's models

Короткий адрес: https://sciup.org/14123320

IDR: 14123320

Список литературы Modelling of Grover's quantum search algorithms: implementations of simple quantum simulators on classical computers

A Fixed-Phase Quantum Search Algorithm with More Flexible Behavior / Х Li [et al.] // J. of Quantum Information Science. – 2012. – No 2. – Pp. 28-34.
Fixed-point quantum search with an optimal number of queries / T. Yoder [et al.] // arXiv:1409.3305v2 [quant-ph]. – 24 Nov 2014.
Zhang, K., Korepin, V. E. Depth optimization of quantum search algorithms beyond Grover’s algorithm // arXiv:1908.04171v3 [quant-ph]. – 27 Mar 2020.
Research on phases of Grover-type algorithms / B.-W. Ma [et al.] // arXiv:1801.07369v1 [quant-ph]. – 23 Jan 2018.
Operating Quantum States in Single Magnetic Molecules: Implementation of Grover’s Quantum Algo-rithm / C. Godfrin [et al.] // arXiv:1710.11229v2 [quant-ph]. – 28 Nov 2017.
A Four-Phase Improvement of Grover’s Algorithm / B.-W. Ma [et al.] // CHIN. PHYS. LETT. – 2017. – Vol. 34. – No.7. – Pp. 07030.
Bose, S., Rallan, L., Vedral, V. Communication Capacity of Quantum Computation // Phys. Rev. Lett. – 2000. – Vol. 85. – Pp. 5448. (available: arXiv: 0003072v1 [quant-ph]. – 17 Mar 2000).
Grover, L. From Schrödinger’s Equation to the Quantum Search Algorithm // arXiv: 0109116 [quant-ph]. – 22 Sep 2001.
Martin-Delgado, M. A. The Schrodinger Equation, Reversibility and the Grover Algorithm // arXiv: /0412130v1 [quant-ph]. – 16 Dec 2004.
Quantum Algorithm Design: Techniques and Applications / C. SHA [et al.] // J Syst Sci Complex. – 2019. – Vol. 32. – Pp. 375–452.
Bausch, J. Fast Black-Box Quantum State Preparation // arXiv:2009.10709v1 [quant-ph]. – 22 Sep 2020.
Meyer, D. A., Wong, T. G. Nonlinear quantum search using the Gross-Pitaevskii equation // New Jour-nal of Physics. – 2013. – Vol. 15. – No 6. – Pp. 063014.
Wong, T. G. Nonlinear Quantum Search. A dissertation submitted in partial satisfaction of the require-ments for the degree Doctor of Philosophy in Physics. – University of California, San Diego. – 2014.
Meyer, D. A., Wong, T. G. Quantum search with general nonlinearities // Physical rewiew. – 2014. – Vol. A 89. – Pp. 012312.
Sarkar, A. Quantum Algorithms for pattern-matching in genomic sequences // Master of Science in Computer Engineering at the Delft University of Technology. – 2018.
Quantum Simulation Logic, Oracles, and the Quantum Advantage / N. Johansson [et al.] // Entropy. – 2019. – Vol. 21. – Pp. 800 [doi:10.3390/e21080800].
Nonlinear quantum search via coined quantum walks / B. Herzo [et al.] // arXiv:2009.07800v1 [quant-ph]. – 16 Sep 2020.
Saleh, S. Q., Younes, A. Analyzing the reliability of quantum amplitude amplification techniques in the presence of noise // Electronic Journal of Mathematical Analysis and Applications. – 2020. – Vol. 8. – No 1. – Pp. 162–181.
Pati, A. K. Super Quantum Search Algorithm with Weak Value Amplification and Postselection // arXiv:1910.12390v2 [quant-ph]. – 4 Nov 2019.
Characterization of exact one-query quantum algorithms / W. Chen [et al.] // arXiv:1912.03493v2 [quant-ph]. – 23 Feb 2020.
Characterization of exact one-query quantum algorithms (ii): for partial functions / Z. Ye [et al.] // arXiv:2008.11998v1 [quant-ph]. – 27 Aug 2020.
A multi-step quantum algorithm for solving problems with a special structure / H. Wang [et al.] // arXiv:1912.06959v2 [quant-ph]. – 20 Aug 2020.
Hunt, S., Gadouleau, M. Grover’s Algorithm and Many-Valued Quantum Logic // arXiv:2001.06316v1 [cs.DS]. – 17 Jan 2020.
Quantum Search with Prior Knowledge / X. He [et al.] // arXiv:2009.08721v1 [quant-ph]. – 18 Sep 2020.
An Optimized Quantum Maximum or Minimum Searching Algorithm and its Circuits / Y. Chen [et al.] // arXiv:1908.0794308721v1 [quant-ph]. – 18 Sep 2019.
Tsurumaru, T. Equivalence of three quantum algorithms: Privacy amplification, error correction, and data compression // arXiv:2009.08823v1 [quant-ph]. – 18 Sep 2020.
Transition Probabilities in Generalized Quantum Search Hamiltonian Evolutions / S. Gassner [et al.] // arXiv:2002.02242v1 [quant-ph]. – 6 Feb 2020.
Optimizing Quantum Search Using a Generalized Version of Grover’s Algorithm / A. Gilliam [et al.] // arXiv:2005.06468v2 [quant-ph]. – 26 May 2020.
Introducing structure to expedite quantum search / M. Brianski [et al.] // arXiv:2006.05828v1 [quant-ph]. – 10 Jun 2020.
Quantum Search for Scaled Hash Function Preimages / S. Ramos-Calderer [et al.] // arXiv:2009.00621v1 [quant-ph]. – 1 Sep 2020.
Number Partitioning with Grover’s Algorithm in Central Spin Systems / G. Anikeev [et al.] // arXiv:2009.05549v1 [quant-ph]. – 11 Sep 2020.
Tutorial: Gate-based superconducting quantum computing / S. Kwon [et al.] // arXiv:2009.08021v1 [quant-ph]. – 17 Sep 2020.
Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation / A. Bärtschi [et al.] // arXiv:2006.00354v1 [quant-ph]. – 30 May 2020.
Benchmarking 16-element quantum search algorithms on IBM quantum processors / J. Gwinner [et al.] // arXiv:2007.06539v1 [quant-ph]. – 13 Jul 2020.
Quantum Circuits for Sparse Isometries / E. Malvetti [et al.] // arXiv:2006.00016v1 [quant-ph]. – 29 May 2020.
Brickman, K.-A. Implementation of Grover’s quantum search algorithm with two trapped cadmium ions // A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philoso-phy (Physics) in The University of Michigan. – 2007.
Dewes, A. Demonstrating quantum speed-up with a two-transmon quantum processor. Superconductivi-ty [cond-mat.supr-con]. – Université Pierre et Marie Curie. – Paris VI, 2012.
Quantum search for scaled Hash function preimages / S. Ramos-Calderer [et al.] // arXiv:2009.00621v1 [quant-ph]. – 1 Sep 2020.
An Optimized Quantum Maximum or Minimum Searching Algorithm and its Circuits / Y. Chen [et al.] // arXiv: 1908.07943 [quant-ph]. – 2019.
Qibo: a framework for quantum simulation with hardware acceleration / S. Efthymiou [et al.] // arXiv:2009.01845v1 [quant-ph]. – 3 Sep 2020.
Introduction to Coding Quantum Algorithms: A Tutorial Series Using Qiskit / D. Koch [et al.] // arXiv:1903.04359v1 [quant-ph]. – 7 Mar 2019.
Exploring a Double Full-Stack Communications-Enabled Architecture for Multi-Core Quantum Com-puters / S. Rodrigo [et al.] // arXiv:2009.08186v1 [quant-ph]. – 17 Sep 2020.
Practical Quantum Computing: The value of local computation / J. R. Cruise [еt al.] // arXiv:2009.08513v1 [quant-ph]. – 17 Sep 2020.
Suksmono, A., Minato, Yu. Finding high-order Hadamard matrices by using quantum computers // arXiv:2009.10919v1 [quant-ph]. – 23 Sep 2020.

Еще

Статья научная