КФУ. Карточка публикации. Quantum and stochastic branching programs of bounded width

КАЗАНСКИЙ
ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

RUS

- EN
- 中文
- ES

QUANTUM AND STOCHASTIC BRANCHING PROGRAMS OF BOUNDED WIDTH

Форма представления

Статьи в зарубежных журналах и сборниках

Год публикации

2002

Язык

русский

Авторы, сотрудники КФУ

Аблаев Фарид Мансурович, автор

Библиографическое описание на языке оригинала

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

Аннотация

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

Ключевые слова

quantum computations

Название журнала

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

Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на эту карточку

https://repository.kpfu.ru/?p_id=303535

Полная запись метаданных

Поле DC	Значение	Язык
dc.contributor.author	Аблаев Фарид Мансурович	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/?p_id=303535	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	Статьи в зарубежных журналах и сборниках	ru_RU