A quantum algorithm for string matching

Abstract Algorithms that search for a pattern within a larger data-set appear ubiquitously in text and image processing. Here, we present an explicit, circuit-level implementation of a quantum pattern-matching algorithm that matches a search string (pattern) of length M inside a longer text of lengt...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Pradeep Niroula, Yunseong Nam
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2021
Materias:	Physics QC1-999 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/6828c2dd1cda4927b745961345585041
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:6828c2dd1cda4927b745961345585041
record_format	dspace
spelling	oai:doaj.org-article:6828c2dd1cda4927b7459613455850412021-12-02T10:54:16ZA quantum algorithm for string matching10.1038/s41534-021-00369-32056-6387https://doaj.org/article/6828c2dd1cda4927b7459613455850412021-02-01T00:00:00Zhttps://doi.org/10.1038/s41534-021-00369-3https://doaj.org/toc/2056-6387Abstract Algorithms that search for a pattern within a larger data-set appear ubiquitously in text and image processing. Here, we present an explicit, circuit-level implementation of a quantum pattern-matching algorithm that matches a search string (pattern) of length M inside a longer text of length N. Our algorithm has a time complexity of $$\tilde{O}(\sqrt{N})$$ O ̃ ( N ) , while the space complexity remains modest at O(N + M). We report the quantum gate counts relevant for both pre-fault-tolerant and fault-tolerant regimes.Pradeep NiroulaYunseong NamNature PortfolioarticlePhysicsQC1-999Electronic computers. Computer scienceQA75.5-76.95ENnpj Quantum Information, Vol 7, Iss 1, Pp 1-5 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Physics QC1-999 Electronic computers. Computer science QA75.5-76.95
spellingShingle	Physics QC1-999 Electronic computers. Computer science QA75.5-76.95 Pradeep Niroula Yunseong Nam A quantum algorithm for string matching
description	Abstract Algorithms that search for a pattern within a larger data-set appear ubiquitously in text and image processing. Here, we present an explicit, circuit-level implementation of a quantum pattern-matching algorithm that matches a search string (pattern) of length M inside a longer text of length N. Our algorithm has a time complexity of $$\tilde{O}(\sqrt{N})$$ O ̃ ( N ) , while the space complexity remains modest at O(N + M). We report the quantum gate counts relevant for both pre-fault-tolerant and fault-tolerant regimes.
format	article
author	Pradeep Niroula Yunseong Nam
author_facet	Pradeep Niroula Yunseong Nam
author_sort	Pradeep Niroula
title	A quantum algorithm for string matching
title_short	A quantum algorithm for string matching
title_full	A quantum algorithm for string matching
title_fullStr	A quantum algorithm for string matching
title_full_unstemmed	A quantum algorithm for string matching
title_sort	quantum algorithm for string matching
publisher	Nature Portfolio
publishDate	2021
url	https://doaj.org/article/6828c2dd1cda4927b745961345585041
work_keys_str_mv	AT pradeepniroula aquantumalgorithmforstringmatching AT yunseongnam aquantumalgorithmforstringmatching AT pradeepniroula quantumalgorithmforstringmatching AT yunseongnam quantumalgorithmforstringmatching
_version_	1718396473459081216

A quantum algorithm for string matching

Ejemplares similares