Skip to main content
Top
Published in:
Cover of the book

2021 | OriginalPaper | Chapter

Implementing Quantum Finite Automata Algorithms on Noisy Devices

Authors : Utku Birkan, Özlem Salehi, Viktor Olejar, Cem Nurlu, Abuzer Yakaryılmaz

Published in: Computational Science – ICCS 2021

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

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 \(\mathtt {MOD}_\mathrm{p}= \{{a^{j}} \mid {j \equiv 0 \mod p}\} \) with bounded error, where p is a prime number. In this paper we present improved circuit based implementations for QFA algorithms recognizing the \(\mathtt {MOD}_\mathrm{p}\) problem using the Qiskit framework. We focus on the case \(p=11\) and provide a 3 qubit implementation for the \(\mathtt {MOD}_\mathrm{11}\) 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 \(\mathtt {MOD}_\mathrm{31}\).

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Footnotes
1
The set of basis gates was changed to CX, I, \(R_z\), \(\sqrt{X}\), X in January 2021.
 
Literature
2.
go back to reference Ajtai, M., Iwaniec, H., Komlós, J., Pintz, J., Szemerédi, E.: Construction of a thin set with small Fourier coefficients. Bull. Lond. Math. Soc. 22(6), 583–590 (1990)MathSciNetCrossRef Ajtai, M., Iwaniec, H., Komlós, J., Pintz, J., Szemerédi, E.: Construction of a thin set with small Fourier coefficients. Bull. Lond. Math. Soc. 22(6), 583–590 (1990)MathSciNetCrossRef
3.
go back to reference Ambainis, A., Freivalds, R.: 1-way quantum finite automata: strengths, weaknesses and generalizations. In: 39th Annual Symposium on Foundations of Computer Science, FOCS 1998, pp. 332–341. IEEE Computer Society (1998) Ambainis, A., Freivalds, R.: 1-way quantum finite automata: strengths, weaknesses and generalizations. In: 39th Annual Symposium on Foundations of Computer Science, FOCS 1998, pp. 332–341. IEEE Computer Society (1998)
4.
go back to reference Ambainis, A., Nahimovs, N.: Improved constructions of quantum automata. Theor. Comput. Sci. 410(20), 1916–1922 (2009)MathSciNetCrossRef Ambainis, A., Nahimovs, N.: Improved constructions of quantum automata. Theor. Comput. Sci. 410(20), 1916–1922 (2009)MathSciNetCrossRef
6.
go back to reference Barenco, A., et al.: Elementary gates for quantum computation. Phys. Rev. A 52(5), 3457–3467 (1995)CrossRef Barenco, A., et al.: Elementary gates for quantum computation. Phys. Rev. A 52(5), 3457–3467 (1995)CrossRef
7.
go back to reference Kālis, M.: Kvantu Algoritmu Realizācija Fiziskā Kvantu Datorā (Quantum Algorithm Implementation on a Physical Quantum Computer). Master’s thesis, University of Latvia (2018) Kālis, M.: Kvantu Algoritmu Realizācija Fiziskā Kvantu Datorā (Quantum Algorithm Implementation on a Physical Quantum Computer). Master’s thesis, University of Latvia (2018)
8.
go back to reference Mereghetti, C., Palano, B., Cialdi, S., Vento, V., Paris, M.G.A., Olivares, S.: Photonic realization of a quantum finite automaton. Phys. Rev. Res. 2(1), 013089–013103 (2020)CrossRef Mereghetti, C., Palano, B., Cialdi, S., Vento, V., Paris, M.G.A., Olivares, S.: Photonic realization of a quantum finite automaton. Phys. Rev. Res. 2(1), 013089–013103 (2020)CrossRef
9.
go back to reference Moore, C., Crutchfield, J.P.: Quantum automata and quantum grammars. Theor. Comput. Sci. 237(1–2), 275–306 (2000)MathSciNetCrossRef Moore, C., Crutchfield, J.P.: Quantum automata and quantum grammars. Theor. Comput. Sci. 237(1–2), 275–306 (2000)MathSciNetCrossRef
10.
go back to reference Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information: 10th Anniversary Edition, 10th edn. Cambridge University Press, USA (2011) Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information: 10th Anniversary Edition, 10th edn. Cambridge University Press, USA (2011)
11.
go back to reference Sipser, M.: Introduction to the Theory of Computation, 1st edn. International Thomson Publishing (1996) Sipser, M.: Introduction to the Theory of Computation, 1st edn. International Thomson Publishing (1996)
12.
go back to reference Tian, Y., Feng, T., Luo, M., Zheng, S., Zhou, X.: Experimental demonstration of quantum finite automaton. npj Quant. Inf. 5(56), 1–5 (2019) Tian, Y., Feng, T., Luo, M., Zheng, S., Zhou, X.: Experimental demonstration of quantum finite automaton. npj Quant. Inf. 5(56), 1–5 (2019)
Metadata
Title
Implementing Quantum Finite Automata Algorithms on Noisy Devices
Authors
Utku Birkan
Özlem Salehi
Viktor Olejar
Cem Nurlu
Abuzer Yakaryılmaz
Copyright Year
2021
DOI
https://doi.org/10.1007/978-3-030-77980-1_1

Premium Partner