Implementing Quantum Finite Automata Algorithms on Noisy Devices

Birkan U., Salehi Ö., Olejar V., Nurlu C., Yakaryılmaz A.

21st International Conference on Computational Science, ICCS 2021, Virtual, Online, 16 - 18 Haziran 2021, ss.3-16 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası:
  • Doi Numarası: 10.1007/978-3-030-77980-1_1
  • Basıldığı Şehir: Virtual, Online
  • Sayfa Sayıları: ss.3-16
  • Anahtar Kelimeler: Quantum algorithms, Quantum circuit, Quantum finite automata, Rotation gate
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

© 2021, Springer Nature Switzerland AG.Quantum finite automata (QFAs) literature offers an alternative mathematical model for studying quantum systems with finite memory. As a superiority of quantum computing, QFAs have been shown exponentially more succinct on certain problems such as recognizing the language MODp={aj∣j≡0modp} with bounded error, where p is a prime number. In this paper we present improved circuit based implementations for QFA algorithms recognizing the MODp problem using the Qiskit framework. We focus on the case p= 11 and provide a 3 qubit implementation for the MOD11 problem reducing the total number of required gates using alternative approaches. We run the circuits on real IBM quantum devices but due to the limitation of the real quantum devices in the NISQ era, the results are heavily affected by the noise. This limitation reveals once again the need for algorithms using less amount of resources. Consequently, we consider an alternative 3 qubit implementation which works better in practice and obtain promising results even for the problem MOD31.