Size of quantum versus deterministic finite automata

Andris Ambainis; Uldis Barbans; Agnese Belousova; Aleksandrs Belovs; Ilze Dzelme; Ǧirts Folkmanis; Rusiņš Freivalds; Peteris Lediņš; Rihards Opmanis; Agnis Škuškovniks

Size of quantum versus deterministic finite automata

Andris Ambainis^*
, Uldis Barbans
, Agnese Belousova
, Aleksandrs Belovs
, Ilze Dzelme
, Ǧirts Folkmanis
, Rusiņš Freivalds
, Peteris Lediņš
, Rihards Opmanis
, Agnis Škuškovniks

^*Corresponding author for this work

University of Latvia

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

1 Citation (Scopus)

Abstract

A.Ambainis and R.Freivalds found that for some languages QFA can have exponential size advantages. They used a language in a single-letter alphabet to prove these advantages. We improve the base of the exponent in these advantages by using more complicated languages in more rich alphabets.

Original language	English
Title of host publication	Proceedings of the International Conference on VLSI, VLSI 03
Editors	H.R. Arbania, L.T. Yang
Pages	303-308
Number of pages	6
Publication status	Published - 2003
Externally published	Yes
Event	Proceedings of the International Conference on VLSI, VLSI'03 - Las Vegas, NV, United States Duration: 23 Jun 2003 → 26 Jun 2003

Publication series

Name	Proceedings of the International Conference on VLSI

Conference

Conference	Proceedings of the International Conference on VLSI, VLSI'03
Country/Territory	United States
City	Las Vegas, NV
Period	23/06/03 → 26/06/03

Keywords

Codes
Finite automata
Quantum computation

Cite this

Ambainis, A., Barbans, U., Belousova, A., Belovs, A., Dzelme, I., Folkmanis, Ǧ., Freivalds, R., Lediņš, P., Opmanis, R., & Škuškovniks, A. (2003). Size of quantum versus deterministic finite automata. In H. R. Arbania, & L. T. Yang (Eds.), Proceedings of the International Conference on VLSI, VLSI 03 (pp. 303-308). (Proceedings of the International Conference on VLSI).

@inproceedings{94954e43ae4f46eeb5a6f40285068a12,

title = "Size of quantum versus deterministic finite automata",

abstract = "A.Ambainis and R.Freivalds found that for some languages QFA can have exponential size advantages. They used a language in a single-letter alphabet to prove these advantages. We improve the base of the exponent in these advantages by using more complicated languages in more rich alphabets.",

keywords = "Codes, Finite automata, Quantum computation",

author = "Andris Ambainis and Uldis Barbans and Agnese Belousova and Aleksandrs Belovs and Ilze Dzelme and Ǧirts Folkmanis and Rusiņ{\v s} Freivalds and Peteris Lediņ{\v s} and Rihards Opmanis and Agnis {\v S}ku{\v s}kovniks",

year = "2003",

language = "English",

isbn = "1932415106",

series = "Proceedings of the International Conference on VLSI",

pages = "303--308",

editor = "H.R. Arbania and L.T. Yang",

booktitle = "Proceedings of the International Conference on VLSI, VLSI 03",

note = "Proceedings of the International Conference on VLSI, VLSI'03 ; Conference date: 23-06-2003 Through 26-06-2003",

}

Ambainis, A, Barbans, U, Belousova, A, Belovs, A, Dzelme, I, Folkmanis, Ǧ, Freivalds, R, Lediņš, P, Opmanis, R & Škuškovniks, A 2003, Size of quantum versus deterministic finite automata. in HR Arbania & LT Yang (eds), Proceedings of the International Conference on VLSI, VLSI 03. Proceedings of the International Conference on VLSI, pp. 303-308, Proceedings of the International Conference on VLSI, VLSI'03, Las Vegas, NV, United States, 23/06/03.

Size of quantum versus deterministic finite automata. / Ambainis, Andris; Barbans, Uldis; Belousova, Agnese et al.
Proceedings of the International Conference on VLSI, VLSI 03. ed. / H.R. Arbania; L.T. Yang. 2003. p. 303-308 (Proceedings of the International Conference on VLSI).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

TY - GEN

T1 - Size of quantum versus deterministic finite automata

AU - Ambainis, Andris

AU - Barbans, Uldis

AU - Belousova, Agnese

AU - Belovs, Aleksandrs

AU - Dzelme, Ilze

AU - Folkmanis, Ǧirts

AU - Freivalds, Rusiņš

AU - Lediņš, Peteris

AU - Opmanis, Rihards

AU - Škuškovniks, Agnis

PY - 2003

Y1 - 2003

N2 - A.Ambainis and R.Freivalds found that for some languages QFA can have exponential size advantages. They used a language in a single-letter alphabet to prove these advantages. We improve the base of the exponent in these advantages by using more complicated languages in more rich alphabets.

AB - A.Ambainis and R.Freivalds found that for some languages QFA can have exponential size advantages. They used a language in a single-letter alphabet to prove these advantages. We improve the base of the exponent in these advantages by using more complicated languages in more rich alphabets.

KW - Codes

KW - Finite automata

KW - Quantum computation

UR - https://www.scopus.com/pages/publications/12144287588

M3 - Conference paper

AN - SCOPUS:12144287588

SN - 1932415106

T3 - Proceedings of the International Conference on VLSI

SP - 303

EP - 308

BT - Proceedings of the International Conference on VLSI, VLSI 03

A2 - Arbania, H.R.

A2 - Yang, L.T.

T2 - Proceedings of the International Conference on VLSI, VLSI'03

Y2 - 23 June 2003 through 26 June 2003

ER -

Size of quantum versus deterministic finite automata

Abstract

Publication series

Conference

Keywords

Other files and links

Fingerprint

Cite this