Indian Journal of Pure and Applied Physics

Open Access Open Access  Restricted Access Subscription Access

Noise Analysis of Grover'sQuantum Search Algorithm


Affiliations
1 Department of Electronics and Communication Engineering,SLIET, Longowal, Punjab 148 106, India., India
2 Centre for Development of Advanced Computing (C-DAC), Mohali, Punjab 160 071, India., India
 

For searching an item in unstructured databases, Grover'squantum search algorithm offers quadratic speedup over classical search algorithms. This paper reports 2 to 5 quantum-bit (Qubit) implementations ofGrover's search algorithm using the phase-flip method for oracle function realization without any extra ancilla qubit. A comprehensive estimation and analysis of the theoretical and physical accuracies of the algorithm have been presented. The impact of increasing qubits on accuracy has been computed and analyzed. The metrics delineated for comparison are the number of qubits and gates, depth of the circuit, execution time, and theoretical/physical accuracy. The results revealed a greater disparity between theoretical and physical accuracy using a higher number of qubits perceived to be caused by noisy qubits utilized in computations. The novelty of the work is the investigation of variations caused bythe noise in the accuracy and execution time of Grover's search algorithm. The results indicate that because of noise, the accuracy of 2- and 3- qubit implementations declined by 14.49% and 33.86%, whereas the execution time increased by 50% and 80%; respectively.

Keywords

Grover’s Algorithm, Initialization, Oracl, Amplitude Amplification, CNOT, Qubit, Phase-Flip, Noise.
User
Notifications
Font Size

  • Ladd T D, Jelezko F, LaflammeR, Nakamura Y, Monroe C & O'Brien J L, Nature, 464 (2010) 45.

  • Saini S, Khosla P, Kaur M & Singh G, Int J Theor Phys, 59 (2020) 4013.

  • Mandviwalla A, Ohshiro K, et al., International Conference on Big Data (Big Data), IEEE, USA, (2018) 2531.

  • Singh G, Kaur M, Singh M & Kumar Y, Indian J Pure Appl Phys, 60 (2022) 407.

  • Szalay A S, Gray J & Vanden Berg J, Proc SPIE, 4836 (2002) 33.

  • Wolf R de, Ethics Info Technol J, 19 (2017) 271.

  • Harrow A W, Hassidim A & Lloyd S, Phy Rev Lett, 103 (2009) 150502.

  • Shor P W, Proc 35th Annual Symposium on Foundations of Computer Science, IEEE, USA, (1994) 124.

  • Grover L K, Proc 28th Annual ACM Symposium on the Theory of Computation, ACM Press, USA, (1996) 212.

  • Rieffel E & Polak W, ACM Comput Surv, 32 (2000) 300.

  • Nagy M & Akl S G, Int J Parallel Emergent Distrib Syst, 21 (2006) 1.

  • Nielsen M A & Chuang I L, Quantum Computation and Quantum Information, (Cambridge University Press, UK), 10 th Edn, 2010.

  • Acampora G et al., Inf Fusion, 89 (2023) 16.

  • Kumar T, Kumar D, Singh G, Indian J Pure Appl Phys,60 (2022) 644.

  • Kumar T et al., Chinese J Phys, 83 (2023) 277.

  • IBM Inc, Ibmq_qasm_simulator.http://quantum-computing.ibm.com/?system=ibmq_qasm_simulator.

  • IBM Inc., Ibmq_santiago. https://quantum-computing. ibm.com/ ?system=ibmq_santiago.

  • Coles P J, Eidenbenz S, Pakin S, Adedoyin A, Ambrosiano J, et al., arXiv preprint arXiv:1804.03719, (2018).

  • Hu W,Natural Science, 10 (2018) 45.

  • Figgatt C, Maslov D, Landsman K, et al., Nature Commun J, 8 (2017)1918.

  • Stromberg P & Karlsson V B, 4-qubit Grover's algorithm implemented for the ibmqx5 architecture, Degree project, KTH royal institute of technology, Sweden, 2018.

  • Simon D R, SIAM J Comput, 26 (1997) 1474.

  • Jozsa R, arXivpreprint quant-ph/9901021, (1999).

  • Lloyd S, Mohseni M & Rebentrost R, arXiv:1307.0411v2 [quant-ph], (2013).

  • Nahimovs N & Rivošs A, Sci Papers Univ Latvia, 756 (2010) 221.

  • Kwiat P G et al., J Mod Opt, 47 (2000) 257.

  • Zalka C, Phys Rev A, 60 (1999) 2746.

  • IBM Inc, Quantum information science kit- Grover'sAlgorithm.https://qiskit.org/textbook/ch-algorithms/grover.html.

  • IBM Inc, IBM quantum experience.https:// quantumexperience.ng.bluemix.net/qx/experience.

  • Mitarai K, Negoro M, Kitagawa M & Fujii K, Phys Rev A, 98 (2018) 032309.

  • IBM Inc, Quantum information science kit. https://qiskit.org/aqua.

  • Chen Y T, Farquhar C &Parrish R M, NPJ Quantum Inf, 7 (2021) 61.

  • Chaudhary et al., arXiv:1908.05154 [quant-ph], (2019).

  • Gawron P, et al., Int J Appl Math Comput Sci, 22 (2012) 493–499.

  • Amaral G C et al., Quantum Inf Process, 18 (2019) 342.


Abstract Views: 65

PDF Views: 52




  • Noise Analysis of Grover'sQuantum Search Algorithm

Abstract Views: 65  |  PDF Views: 52

Authors

Tarun Kumar
Department of Electronics and Communication Engineering,SLIET, Longowal, Punjab 148 106, India., India
Dilip Kumar
Department of Electronics and Communication Engineering,SLIET, Longowal, Punjab 148 106, India., India
Gurmohan Singh
Centre for Development of Advanced Computing (C-DAC), Mohali, Punjab 160 071, India., India

Abstract


For searching an item in unstructured databases, Grover'squantum search algorithm offers quadratic speedup over classical search algorithms. This paper reports 2 to 5 quantum-bit (Qubit) implementations ofGrover's search algorithm using the phase-flip method for oracle function realization without any extra ancilla qubit. A comprehensive estimation and analysis of the theoretical and physical accuracies of the algorithm have been presented. The impact of increasing qubits on accuracy has been computed and analyzed. The metrics delineated for comparison are the number of qubits and gates, depth of the circuit, execution time, and theoretical/physical accuracy. The results revealed a greater disparity between theoretical and physical accuracy using a higher number of qubits perceived to be caused by noisy qubits utilized in computations. The novelty of the work is the investigation of variations caused bythe noise in the accuracy and execution time of Grover's search algorithm. The results indicate that because of noise, the accuracy of 2- and 3- qubit implementations declined by 14.49% and 33.86%, whereas the execution time increased by 50% and 80%; respectively.

Keywords


Grover’s Algorithm, Initialization, Oracl, Amplitude Amplification, CNOT, Qubit, Phase-Flip, Noise.

References