KFU. Card publication. Quantum and stochastic branching programs of bounded width

KAZAN
FEDERAL UNIVERSITY

- RUS
- 中文
- ES

QUANTUM AND STOCHASTIC BRANCHING PROGRAMS OF BOUNDED WIDTH

Form of presentation

Articles in international journals and collections

Year of publication

2002

Язык

русский

Authors, employees of KFU

Ablaev Farid Mansurovich, author

Bibliographic description in the original language

F Ablayev, C Moore, C Pollett Quantum and stochastic branching programs of bounded width // Automata, Languages and Programming: 29th International Colloquium, ICALP 2002 Málaga, Spain, July 8–13, 2002 Proceedings 29

Annotation

Automata, Languages and Programming: 29th International Colloquium, ICALP

Keywords

quantum computations

The name of the journal

Automata, Languages and Programming: 29th International Colloquium, ICALP

Please use this ID to quote from or refer to the card

https://repository.kpfu.ru/eng/?p_id=303535&p_lang=2

Full metadata record

Field DC	Value	Language
dc.contributor.author	Ablaev Farid Mansurovich	ru_RU
dc.date.accessioned	2002-01-01T00:00:00Z	ru_RU
dc.date.available	2002-01-01T00:00:00Z	ru_RU
dc.date.issued	2002	ru_RU
dc.identifier.citation	F Ablayev, C Moore, C Pollett Quantum and stochastic branching programs of bounded width // Automata, Languages and Programming: 29th International Colloquium, ICALP 2002 Málaga, Spain, July 8–13, 2002 Proceedings 29	ru_RU
dc.identifier.uri	https://repository.kpfu.ru/eng/?p_id=303535&p_lang=2	ru_RU
dc.description.abstract	Automata, Languages and Programming: 29th International Colloquium, ICALP	ru_RU
dc.description.abstract	We prove upper and lower bounds on the power of quantum and stochastic branching programs of bounded width. We show any NC1 language can be accepted exactly by a width-2 quantum branching program of polynomial length, in contrast to the classical case where width 5 is necessary unless NC1 = ACC. This separates width-2 quantum programs from width-2 doubly stochastic programs as we show the latter cannot compute the middle bit of multiplication. Finally, we show that bounded-width quantum and stochastic programs can be simulated by classical programs of larger but bounded width, and thus are in NC1.	ru_RU
dc.language.iso	ru	ru_RU
dc.subject		ru_RU
dc.title	Quantum and stochastic branching programs of bounded width	ru_RU
dc.type	Articles in international journals and collections	ru_RU