E-Book Overview
Казань: Казанский Федеральный Университет. - 2010. - 37 стр.
Статья представляет описание модели квантовых вычисления для одного класса программ.<strong>Содержание: Вычисления в модели ветвящихся программ Методы построения эффективных квантовых алгоритмов и нижние оценки сложности их представления Математическое описание класса задач, эффективно решаемых квантовыми ветвящимися программами Литература
E-Book Content
Êëàññè÷åñêèå è êâàíòîâûå âåòâÿùèåñÿ ïðîãðàììû Àáëàåâ Ô.Ì.
Âàñèëüåâ À.Â.
Îãëàâëåíèå
1
Âû÷èñëåíèÿ â ìîäåëè âåòâÿùèõñÿ ïðîãðàìì
1.1 1.2 1.3 1.4 1.5 1.6 1.7
1.8
2
2
Âû÷èñëèòåëüíûå çàäà÷è, ÿçûêè è áóëåâû ôóíêöèè. . . . . . . . . Ìîäåëè âû÷èñëåíèé. . . . . . . . . . . . . . . . . . . . . . . . . . . Ìåðû ñëîæíîñòè. . . . . . . . . . . . . . . . . . . . . . . . . . . . Êîíòàêòíûå ñõåìû . . . . . . . . . . . . . . . . . . . . . . . . . . . Äåòåðìèíèðîâàííàÿ âåòâÿùàÿñÿ ïðîãðàììà . . . . . . . . . . . . Âåðîÿòíîñòíàÿ âåòâÿùàÿñÿ ïðîãðàììà . . . . . . . . . . . . . . . Âåòâÿùèåñÿ ïðîãðàììû ñ îãðàíè÷åíèÿìè . . . . . . . . . . . . . . 1.7.1 ×èòàþùèå îäèí ðàç âåòâÿùèåñÿ ïðîãðàììû . . . . . . . . 1.7.2 ×èòàþùèå k ðàç âåòâÿùèåñÿ ïðîãðàììû . . . . . . . . . . 1.7.3 Óïîðÿäî÷åííûå âåòâÿùèåñÿ äèàãðàììû ðåøåíèé (OBDD) 1.7.4 k -OBDD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7.5 Ïðàêòè÷åñêàÿ çíà÷èìîñòü OBDD . . . . . . . . . . . . . . 1.7.6 Ëèíåéíàÿ âåòâÿùàÿñÿ ïðîãðàììà . . . . . . . . . . . . . . 1.7.7 Ëèíåéíîå ïðåäñòàâëåíèå çàáûâàþùåé DBP. . . . . . . . Êâàíòîâàÿ âåòâÿùàÿñÿ ïðîãðàììà . . . . . . . . . . . . . . . . . . 1.8.1 Ñõåìíîå ïðåäñòàâëåíèå . . . . . . . . . . . . . . . . . . . . 1.8.2 Ýôôåêòèâíûå êâàíòîâûå âåòâÿùèåñÿ ïðîãðàììû. . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .
. 2 . 3 . 3 . 3 . 4 . 6 . 7 . 7 . 7 . 7 . 7 . 7 . 8 . 9 . 9 . 10 . 11
Ìåòîäû ïîñòðîåíèÿ ýôôåêòèâíûõ êâàíòîâûõ àëãîðèòìîâ è íèæíèå îöåíêè ñëîæíîñòè èõ ïðåäñòàâëåíèÿ
2.1 2.2
3
16
Îáîáùåííàÿ íèæíÿÿ îöåíêà . . . . . . . . . . . . . . . . . . 2.1.1 Ñèíòàêñè÷åñêèå êâàíòîâûå âåòâÿùèåñÿ ïðîãðàììû. 2.1.2 Äîêàçàòåëüñòâî òåîðåìû 2.1.1 . . . . . . . . . . . . . Ìåòîäû ïîñòðîåíèÿ ýôôåêòèâíûõ êâàíòîâûõ àëãîðèòìîâ . 2.2.1 Êâàíòîâûé ìåòîä îòïå÷àòêîâ . . . . . . . . . . . . . . 2.2.2 Ìåòîä Áàððèíãòîíà . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
16 16 17 20 20 24
Ìàòåìàòè÷åñêîå îïèñàíèå êëàññà çàäà÷, ýôôåêòèâíî ðåøàåìûõ êâàíòîâûìè âåòâÿùèìèñÿ ïðîãðàììàìè
3.1 3.2
26
Ýôôåêòèâíûå àëãîðèòìû, îñíîâàííûå íà ìåòîäå îòïå÷àòêîâ . . . . . . . . . . . 26 Ýôôåêòèâíîå âû÷èñëåíèå ôóíêöèé èç êëàññà NC1 . . . . . . . . . . . . . . . . . 28
Ðàñøèðåííûé ñïèñîê ëèòåðàòóðû
28
1
Ãëàâà 1 Âû÷èñëåíèÿ â ìîäåëè âåòâÿùèõñÿ ïðîãðàìì
1.1
Âû÷èñëèòåëüíûå çàäà÷è, ÿçûêè è áóëåâû ôóíêöèè.
 òåîðåòè÷åñêîé è ïðèêëàäíîé êèáåðíåòèêå øèðîêî èñïîëüçóåòñÿ àïïàðàò òåîðèè ÿçûêîâ è áóëåâûõ ôóíêöèé.  òåîðèè ñëîæíîñòè ÿçûêè è áóëåâû ôóíêöèè èñïîëüçóþòñÿ òàêæå äëÿ ïðåäñòàâëåíèÿ âû÷èñëèòåëüíûõ çàäà÷. Ýòî ïîçâîëÿåò èìåòü åäèíîå ïðåäñòàâëåíèå çàäà÷, ÷òî âàæíî ïðè àíàëèçå èõ ñðàâíèòåëüíûõ ñëîæíîñòíûõ õàðàêòåðèñòèê. Îïðåäåëåíèå
1.1.1. Àëôàâèò êîíå÷íîå ìíîæåñòâî