Квантовый конечный автомат - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:42:33Z

rollbackEdits.php mass rollback

185.244.195.157 в 03:33, 1 сентября 2022

2022-09-01T03:33:03Z

Alex Z: Удалено содержимое страницы

2015-01-10T10:49:28Z

Удалено содержимое страницы

213.21.46.69: /* Многомерный квантовый конечный автомат */

2015-01-09T23:28:19Z

‎Многомерный квантовый конечный автомат

213.21.46.69: /* Многомерный квантовый конечный автомат */

2015-01-09T23:24:36Z

‎Многомерный квантовый конечный автомат

213.21.46.69: /* Многомерный квантовый конечный автомат */

2015-01-09T23:15:52Z

‎Многомерный квантовый конечный автомат

213.21.46.69: /* Одномерный квантовый конечный автомат */

2015-01-09T23:10:05Z

‎Одномерный квантовый конечный автомат

213.21.46.69: /* Одномерный квантовый конечный автомат */

2015-01-09T23:09:31Z

‎Одномерный квантовый конечный автомат

213.21.46.69: /* Одномерный квантовый конечный автомат */

2015-01-09T23:07:19Z

‎Одномерный квантовый конечный автомат

213.21.46.69: /* Одномерный квантовый конечный автомат */

2015-01-09T23:06:24Z

‎Одномерный квантовый конечный автомат

← Предыдущая		Версия 16:42, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}

← Предыдущая	Версия 03:33, 1 сентября 2022
Строка 1:	Строка 1:
	+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
	+	\|+
	+	\|-align="center"
	+	\|'''НЕТ ВОЙНЕ'''
	+	\|-style="font-size: 16px;"
	+	\|
	+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

	+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
	+
	+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
	+
	+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
	+
	+	''Антивоенный комитет России''
	+	\|-style="font-size: 16px;"
	+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
	+	\|-style="font-size: 16px;"
	+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
	+	\|}

← Предыдущая		Версия 10:49, 10 января 2015
Строка 1:		Строка 1:
−	Квантовые вычисления сочетает в себе квантовую механику с информатикой. Определяя квантово-механические аналоги обычных моделей вычислений (например : машины Тьюринга или конечный автомат), получаем модели, как правило, более мощные, чем обычные (или классических) модели, потому что квантовая механика позволяет реализовать более широкий спектр операций. Кроме того, квантовые алгоритмы могут быть экспоненциально быстрее, чем любой классического алгоритма.

−	~~== Определение ==~~
−	~~{{Определение~~
−	~~\|definition=~~
−	~~'''Квантовый конечный автомат (ККА)''' (англ. ''Quantum finite automata'', ''QFA'') — квантовый аналог конечного автомата.~~
−	}}
−
−	Объединение квантовой механики с конечным автоматом и является Квантовым конечным автоматом. Кроме того, ККА является частным случаем ''Геометрического конечного автомата'' и ''Топологического конечного автомата''.
−
−	~~===Принцип работы===~~
−	* На вход подается строчка <tex> s = \langle a_0, a_1,.. ,a_k \rangle, a_i \in \Sigma</tex>.
−	* На выходе мы получаем число <tex> Pr(s)</tex>, являющееся вероятностью данного конечного автомата быть в допускающем состоянии.
−
−	~~== Описание==~~
−
−	Для начало воспользуемся графовым представлением [[Детерминированные конечные автоматы\|Детерминированного конечного автомата (ДКА)]]. Пусть в нем <tex>N</tex> вершин и все вершины пронумерованы. Тогда для представления такого графа можно воспользоваться [[Матрица смежности графа\|Матрицей смежности]] <tex>[N \times N]</tex> для каждого символа <tex> c \in \Sigma</tex>, в котором <tex>1</tex> означает переход из состояние <tex>i</tex> в <tex>j</tex> по символу <tex>c</tex>, а <tex>0</tex> - его отсутствие. В этом случаи, текущее состояние автомата записывается как вектор, размерности <tex>N</tex>, в котором будет лишь одна единица, обозначающая текущее положение состояния. При помощи такого описания можно легко делать переходы из нынешнего состояние в новое состояние по символу <tex> c \in \Sigma</tex> обыкновенный ''умножением матриц''.
−
−	* Пусть у нас есть ДКА с <tex>N</tex> вершинами и его <math>\Sigma=\{c_1, c_2, c_3, ..\}</math>. Тогда по описанному определению можно составить матрицы смежности <math>\{U_\alpha \| \alpha \in \Sigma \}</math> размерности <tex>[N \times N]</tex>. Так же введем <tex>N</tex>-размерный вектор <tex>q \in Q</tex>, описывающее состояние ДКА, a <tex>q_0</tex> - начальное состояние автомата. Тогда для перехода из состояния <tex>q_0</tex> в <tex>q</tex> по строчке <tex> s = \langle \alpha_0, \alpha_1,.. \rangle</tex> нужно воспользоваться правилом умножения матриц из линейной алгебры : <math>q = \cdots U_{\alpha_1} U_{\alpha_0} q_0.</math>
−
−	Описанное выше по сути и является ККА, но в <tex>q</tex> записываются [[wikipedia:Probability amplitude\|'''амплитуды вероятностей''']], a матрицы <math>\{U_\alpha\}</math> - [https://ru.wikipedia.org/wiki/Унитарная_матрица '''унитарные матрицы'''].
−	Для ККА характерено геометрическая интерпретация в пространстве <tex>CP^N</tex>. С этой стороны вектор <tex>q</tex> является точкой, a <math>\{U_\alpha\}</math> - [https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%B4%D1%81%D1%82%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%A8%D1%80%D1%91%D0%B4%D0%B8%D0%BD%D0%B3%D0%B5%D1%80%D0%B0 операторы эволюции в представлении Шредингера].
−
−	~~В дополнении для ККА можно упомянуть пару особенностей :~~
−
−	* НКА. Из-за свойство НКА в векторе <tex>q</tex> и в столбцах матриц <math>\{U_\alpha\}</math> может находиться несколько <tex>1</tex>. Если в этом случаи рассмотреть [[Построение по НКА эквивалентного ДКА, алгоритм Томпсона\|алгоритм Томпсона]], то построенные на их основе Квантовые конечные автоматы не будут эквивалентны. Эта проблема является одно научно-исследовательских задач в теории ККА.
−
−	* Вероятностный конечный автомат. Для его построения нужно всего лишь в ККА использовать [https://ru.wikipedia.org/wiki/%D0%A1%D1%82%D0%BE%D1%85%D0%B0%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0 стохастические матрицы] для <math>\{U_\alpha\}</math> и вектор вероятностей состояний для <tex>q</tex>. Одно из свойств <tex>q</tex> - сумма всех элементов равна <tex>1</tex> и для того чтобы во всех переходах сохранялось это свойство и нужны стохастические матрицы.
−
−	~~=== Одномерный квантовый конечный автомат===~~
−	Авторы одномерного (англ. ''Measure-one'', ''1-way'') ККА - Cris Moore и James P. Crutchfield (2000). Главное свойство - допускать [[Регулярные языки: два определения и их эквивалентность \| регулярный язык]].
−	В таком виде конечный автомат с <tex>N</tex> состояниями представляется в виде [https://ru.wikipedia.org/wiki/%D0%9A%D1%83%D0%B1%D0%B8%D1%82 кубита] <math>\|\psi\rangle</math> c N-состояниями. Такой кубит <tex>\in CP^N</tex> и приносит в это пространство метрику <math>\Vert\cdot\Vert</math>.
−	~~Матрицы смежности остаются унитарными, а переход в новое сосояние по символу <tex>\alpha</tex> :~~
−	~~:<math>\|\psi'\rangle</math> = <math>U_\alpha \|\psi\rangle</math>.~~
−	Переход в допускающее состояние производиться [https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B5%D0%BA%D1%82%D0%BE%D1%80_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) матрицей-проектором] <tex> P [N \times N]</tex>.
−
−	~~Вероятность <tex>Pr(s)</tex>, где <tex>s = (a_0,a_1,\cdots,a_k) </tex> равна :~~
−
−	~~:<math>\operatorname{Pr}(s) = \Vert P U_{a_k} \cdots U_{a_1} U_{a_0}\|\psi\rangle\Vert^2 </math>~~
−
−	~~===Многомерный квантовый конечный автомат===~~
−	Многомерный (или Двухмерный) (англ. ''Measure-many'', ''2-way'') ККА был введен Attila Kondacs и John Watrous в 1997. Главное свойство - допускать нерегулярный язык <tex>L = \{a^mb^m\}</tex> за линейное время. Принципы многомерного ККА очень схож с Одномерный, за исключением применение матрицы <tex>P</tex> после каждого итерации символа строки. Для формального определения понадобиться [[Гильбертовы пространства \| гильбертово пространство]]. Пусть у нас есть гильбертово пространство <math>\mathcal{H}_Q</math> :
−
−	<math>\mathcal{H}_Q=\mathcal{H}_a \oplus \mathcal{H}_r \oplus \mathcal{H}_{non}</math> , где <math> \mathcal{H}_a </math>- допускающее пр-во , <math> \mathcal{H}_r </math> - отвергающее пр-во , <math> \mathcal{H}_{non} </math> - промежуточное пр-во. Для каждого пр-ва существует наборы базисных ординальных векторов <tex>Q , Q_a \subset Q, Q_r \subset Q , Q_{non}\subset Q</tex> соответственно :
−
−	:<math>\mathcal{H}_a=\operatorname{span} \{\|q\rangle : \|q\rangle \in Q_a \}, \mathcal{H}_r = ... , \mathcal{H}_{non} = ... </math> , где <math>\operatorname{span}</math> - [https://ru.wikipedia.org/wiki/%D0%92%D0%B5%D0%BA%D1%82%D0%BE%D1%80%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D1%81%D1%82%D0%B2%D0%BE#.D0.9B.D0.B8.D0.BD.D0.B5.D0.B9.D0.BD.D0.B0.D1.8F_.D0.BE.D0.B1.D0.BE.D0.BB.D0.BE.D1.87.D0.BA.D0.B0 линейная оболочка]
−
−	Так же в многомерном ККА присутствуют 3 матрицы-проектора : <math>P_a</math>, <math>P_r</math> и <math> P_{non} </math> для каждого гильбертово пр-ва :
−
−	~~:<math>P_a:\mathcal{H}_Q \to \mathcal{H}_a , P_r = ..., P_{non} = ...</math>~~
−
−	Переход в новое состояние кубита остается таким же, но после каждого перехода кубит коллпасирует в одно из 3 гильбертовых пр-в <math>\mathcal{H}_a, \mathcal{H}_r , \mathcal{H}_{non}</math>. Для того чтобы определить вероятность автомата находиться в допускающем состоянии нужно :
−
−	~~:<math>\operatorname{Pr}_a (s) = \Vert P_a \|\psi\rangle \Vert^2</math>, где <tex>s</tex> - входящая строчка~~
−
−	~~{{Определение~~
−	~~\|definition=~~
−	~~'''Многомерный квантовый конечный автомат''' - это кортеж : <math>(Q;\Sigma, \delta, q_0, Q_a, Q_r)</math>, где~~
−	* <tex>Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_Q</tex>
−	* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова
−	* <tex>\delta : Q\times \Sigma \times Q \to \mathbb{C} </tex> —всюду определённая функция перехода автомата
−	* <tex>q_0</tex> — начальное состояние автомата
−	* <tex>Q_a \subset Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_a</tex>
−	* <tex>Q_r \subset Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_r</tex>
−
−	}}
−
−	~~==Источники информации==~~
−	* Andris Ambainis, [http://www.lu.lv/fileadmin/user_upload/lu_portal/projekti/datorzinatnes_pielietojumi/publikacijas/Ambainis_7_3.pdf QUANTUM FINITE AUTOMATA]
−	* [[wikipedia:Quantum finite automata \| Wikipedia {{---}} Quantum finite automata]]

@@ Строка 44: / Строка 44: @@
 <math>\mathcal{H}_Q=\mathcal{H}_a \oplus \mathcal{H}_r \oplus \mathcal{H}_{non}</math> , где <math> \mathcal{H}_a </math>- допускающее пр-во , <math> \mathcal{H}_r </math> - отвергающее пр-во , <math> \mathcal{H}_{non} </math> - промежуточное пр-во. Для каждого пр-ва существует наборы базисных ординальных векторов <tex>Q , Q_a \subset Q, Q_r \subset Q , Q_{non}\subset Q</tex> соответственно :
-:<math>\mathcal{H}_a=\operatorname{span} \{|q\rangle : |q\rangle \in Q_a \}, \mathcal{H}_r = ... , \mathcal{H}_{non} = ... </math>
+:<math>\mathcal{H}_a=\operatorname{span} \{|q\rangle : |q\rangle \in Q_a \}, \mathcal{H}_r = ... , \mathcal{H}_{non} = ...  </math> , где <math>\operatorname{span}</math> - [https://ru.wikipedia.org/wiki/%D0%92%D0%B5%D0%BA%D1%82%D0%BE%D1%80%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D1%81%D1%82%D0%B2%D0%BE#.D0.9B.D0.B8.D0.BD.D0.B5.D0.B9.D0.BD.D0.B0.D1.8F_.D0.BE.D0.B1.D0.BE.D0.BB.D0.BE.D1.87.D0.BA.D0.B0 линейная оболочка]
 Так же в многомерном ККА присутствуют 3 матрицы-проектора : <math>P_a</math>, <math>P_r</math> и <math> P_{non} </math> для каждого гильбертово пр-ва :

@@ Строка 40: / Строка 40: @@
 ===Многомерный квантовый конечный автомат===
-Многомерный (или Двухмерный) (англ. ''Measure-many'', ''2-way'') ККА был введен Attila Kondacs и John Watrous в 1997. Главное свойство - допускать нерегулярный язык <tex>L = \{a^mb^m\}</tex> за линейное время. Принципы многомерного ККА очень схож с Одномерный, за исключением применение матрицы <tex>P</tex> после каждого итерации символа строки. Для формального определения понадобиться гильбертово пространство. Пусть у нас есть гильбертово пространство <math>\mathcal{H}_Q</math> :
+Многомерный (или Двухмерный) (англ. ''Measure-many'', ''2-way'') ККА был введен Attila Kondacs и John Watrous в 1997. Главное свойство - допускать нерегулярный язык <tex>L = \{a^mb^m\}</tex> за линейное время. Принципы многомерного ККА очень схож с Одномерный, за исключением применение матрицы <tex>P</tex> после каждого итерации символа строки. Для формального определения понадобиться [[Гильбертовы пространства | гильбертово пространство]]. Пусть у нас есть гильбертово пространство <math>\mathcal{H}_Q</math> :
 <math>\mathcal{H}_Q=\mathcal{H}_a \oplus \mathcal{H}_r \oplus \mathcal{H}_{non}</math> , где <math> \mathcal{H}_a </math>- допускающее пр-во , <math> \mathcal{H}_r </math> - отвергающее пр-во , <math> \mathcal{H}_{non} </math> - промежуточное пр-во. Для каждого пр-ва существует наборы базисных ординальных векторов <tex>Q , Q_a \subset Q, Q_r \subset Q , Q_{non}\subset Q</tex> соответственно :

@@ Строка 46: / Строка 46: @@
 :<math>\mathcal{H}_a=\operatorname{span} \{|q\rangle : |q\rangle \in Q_a \}, \mathcal{H}_r = ... , \mathcal{H}_{non} = ... </math>
-Так же в многомерном ККА присутствуют 3 матрицы-проектора, <math>P_a</math>,  <math>P_r</math> and <math>P_{non}</math>для каждого гильбертово пр-ва:
+Так же в многомерном ККА присутствуют 3 матрицы-проектора : <math>P_a</math>, <math>P_r</math> и <math> P_{non} </math> для каждого гильбертово пр-ва :
 :<math>P_a:\mathcal{H}_Q \to \mathcal{H}_a , P_r = ..., P_{non} = ...</math>
@@ Строка 56: / Строка 56: @@
 {{Определение
 |definition=
-'''Многомерный квантовый конечный автомат''' - это кортеж : <math>(Q;\Sigma; \delta; q_0; Q_a; Q_r)</math>, где
+'''Многомерный квантовый конечный автомат''' - это кортеж : <math>(Q;\Sigma, \delta, q_0, Q_a, Q_r)</math>, где
 * <tex>Q</tex> — базисные ортогональные вектора пр-ва <tex>\mathcal{H}_Q</tex>
 * <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова

@@ Строка 30: / Строка 30: @@
 === Одномерный квантовый конечный автомат===
 Авторы одномерного (англ. ''Measure-one'', ''1-way'') ККА - Cris Moore и James P. Crutchfield (2000). Главное свойство - допускать [[Регулярные языки: два определения и их эквивалентность | регулярный язык]].
-В таком виде конечный автомат с <tex>N</tex> состояниями представляется в виде кубита <math>|\psi\rangle</math> c N-состояниями. Такой кубит <tex>\in CP^N</tex> и приносит в это пространство метрику <math>\Vert\cdot\Vert</math>.
+В таком виде конечный автомат с <tex>N</tex> состояниями представляется в виде [https://ru.wikipedia.org/wiki/%D0%9A%D1%83%D0%B1%D0%B8%D1%82 кубита] <math>|\psi\rangle</math> c N-состояниями. Такой кубит <tex>\in CP^N</tex> и приносит в это пространство метрику <math>\Vert\cdot\Vert</math>.
 Матрицы смежности остаются унитарными, а переход в новое сосояние по символу <tex>\alpha</tex> :
 :<math>|\psi'\rangle</math> = <math>U_\alpha |\psi\rangle</math>.