Проблема алгоритмической разрешимости (полуразрешимости) формальных систем и квантовые D-алгоритмы[1]

П.А. Правильщиков,
в.н.с, к.т.н, с.н.с, pavelp@ipu.ru
ИПУ РАН, г. Москва

Приводится описание квантовых D-алгоритмов (QD-алгоритмов), которые «подогнаны» под архитектуру квантового генератора тестов (КГТ). Показано, что КГТ может служить новой вычислительной моделью (теоретическим аналогом) реального квантового ускорителя, регистр которого построен не на кубитах (dim H = 2), а на кунитах (dim H = n). Действующий макет такого ускорителя будет разработан в ИПУ РАН на базе твёрдых полупроводниковых растворов КРТ («кадмий-ртуть-теллур» [1]). Продемонстрировано, что после сведения проблемы разрешимости или неразрешимости к решению проблемы автоматического доказательства теорем, а последнюю проблему можно свести к решению логических уравнений. На примере излагается способ автоматического доказательства теорем в рамках логики первого порядка, а точнее в рамках пропозиционального исчисления путём решения булевых уравнений с использованием QD-алгоритмов.

The description of quantum D-algorithms (QD-algorithms) which are adjusted to architecture of the quantum generator of tests (QTG) is resulted. It is shown that QTG can serve as new computing model (as theoretical analogue) of the real quantum accelerator at which the register is constructed not on qubits (dim H = 2), but on qudits (dim H = n). The real breadboard model of such accelerator will be developed in the Institute of Control Science (the Russian Academy of Sciences) on the basis of the hard semi-conductor solutions CMT ("cadmium-mercury-tellurium" [1]). It is shown that the decisions a problem of resolvability or unsolvability are reduced to the decision of a problem of the automatic proof of theorems. Then the decision of last problem can be reduced to the decision of the logic equations. It is demonstrated on an example how the way of the automatic proof of theorems in frameworks of propositional calculation are reduced to the way of decision of Boolean equations with use of QD-algorithms.

Описание решения логических уравнений с помощью квантовых D-алгоритмов

В первом докладе на данной конференции CAD-CAM-PDM было продемонстрировано, что решение проблемы разрешимости или неразрешимости может быть сведено к решению проблемы автоматического доказательства теорем. Там же было показано, что решение проблемы автоматического доказательства теорем сводится к решению логических уравнений. Так, в тексте первого доклада левую часть уравнения (7) можно рассматривать как некоторую формулу исчисления высказываний. Решив это уравнение, используя некоторый алгоритм, нам нужно определить истинность или ложность этой формулы в рамках данного исчисления. В качестве такого алгоритма здесь будет рассматриваться QD-алгоритм. Этот алгоритм выполняет полный упорядоченный перебор в целях поиска решения, т.е. в поисках хотя бы одного набора X_i, на котором это уравнение выполняется. Учитывая теорему 1, которую мы пытаемся доказать (см. постановку задачи в тексте 1-го доклада), если такой набор X_i сущест-вует и будет найден, то формула в левой части является истинной в рамках исчисления высказывания. Следовательно, тезис теоремы 1 является не верным. Другими словами, теорема де Моргана не верна. Если такой набор X_i не будет найден QD-алгоритмом, т.е. если такой набор X_i не существует, то или , и, следовательно, теорем де Моргана верна.

Теперь следует напомнить, что QD-алгоритм, как и классические последовательные и параллельно-последова-тельные D-алгоритмы [2,3], является полным алгоритмом. Отличие QD-алгоритма от классических состоит в том, что квантовый алгоритм использует новое матричное исчисление кубических комплексов (матричное D-исчисление).
Если в рамках классических D-алгоритмов использовались таблицы истинности и таблица правил выполнения операции a_g, то в рамках матричного D-исчисления используются унитарные матрицы. В частности, используется унитарная блочно-диагональная матрица U_RБ-Д,n, в которой в качестве подматрицы-блока используется элементарная матрица Рота ¾ матрица U^†_R (см. (9) и (10) в первой части доклада). Матрица U^†_R используется для покоординатного выполнения операции a_g. При выполнении классического параллельно-последовательного D-алгоритма на каждом шаге q обычно пересекаются два куба, каждый из которых представлен в виде вектор-строки. Например, в начале выполнения такого алгоритма выступает куб C₀. Для решаемого здесь уравнения и соответствующего ему КУ таким кубом будет куб С₀, имеющий вид:

	1	2	3	4	5	6	7	8	9
C0 =	~	~	~	~	~	~	~	~	1.	(11)

В (11) число N = 9, где N ¾ число дуг в логической сети КУ (см. рис. 1 в 1-й части). В кубе C₀ число N ¾ это число координат куба (рассматривается многомерный куб C₀ в многомерном пространстве, число измерений которого равно N = 9). На первом шаге (q = 1) классического D-алгоритма куб C₀ пересекается с конкатенацией K₃ (K_r = K₃) строк таблицы истинности логического элемента М2 КУ на рис. 1. Элемент М2 отнесён к третьему рангу (r = 3). В качестве такой таблицы истинности выступает табл. 5 элемента М2 ¾ см. 1-ю часть текста доклада. Конкатенация K_r = K₃ имеет вид:

		7	8	9	7	8	9	7	8	9	7	8	9
K3 =	s3,1,1 ‖ s3,1,2 ‖ s3,1,3 ‖ s3,2,4	= 0	0	0	0	1	1	1	0	1	1	1	0	(12)

Сразу же приведём и две другие конкатенации ¾ конкатенацию K₁ (см. табл. 1 и 2) и конкатенацию K₂ (см. табл. 3 и 4):

		1	3	4	1	3	4	2	5	6	2	5	6
K1 =	s1,1,1 ‖ s1,1,2 ‖ s1,2,1 ‖ s1,2,2	0	0	0	1	1	1	0	0	0	1	1	1	(13)

	(y3 & y5)¢												y¢4 Ú y¢6
	3	5	7	3	5	7	3	5	7	3	5	7	4	6	8	4	6	8	4	6	8	4	6	8
K2 =	0	0	1	0	1	1	1	0	1	1	1	0	0	0	1	0	1	1	1	0	1	1	1	0	(14)

На первом шаге (шаге q = 1) осуществляется пересечение: C₀ Ç K₃, где K₃ рассматривается как некоторый куб, записанный в виде вектор-строки. Пересечение: C₀ Ç K₃ имеет вид:

	1	2	3	4	5	6	7	8	9	7	8	9	7	8	9	7	8	9
C0 =	~	~	~	~	~	~	~	~	1	~	~	1	~	~	1	~	~	1
K3 =	~	~	~	~	~	~	0	0	0	0	1	1	1	0	1	1	1	0	(15)
Ç	--	--	--	--	--	--	--	--	--	--	--	--	--	--	--	--	--	--
C1 =	~	~	~	~	~	~	0	0	Æ	0	1	1	1	0	1	1	1	Æ

Заметим, что в (15) куб C₀ (11) записан в форме, удобной для пересечения с K₃(12).Правила покоординатного пересечения, т.е. правила выполнения операции a_g приведены в табл. 6 в 1-й части доклада. В классическом параллельно-последовательном D-алгоритме операция a_g выполняется аппаратно с помощью блока B_j. При выполнении пересечения C₀ Ç K₃ в целях экономии блоков B_j покоординатное пересечение в первых шести координатах не выполняется. Следовательно, потребуется = 12 блоков B_j. Время Dt_q = Dt₁ выполнения первого шага равно 1 вдеп.

При выполнении QD-алгоритма пересечение C₀ Ç K₃ внешне во многом аналогично (15), но в то же время имеются существенные различия. Во-первых, в соответствии с рис. 2 (см. 1-ю часть) кубы, в частности, куб С₀ размещается в одном куните в виде вектор-столбца. Но запись каждого вектор-столбца в тексте чрезвычайно громоздка. Поэтому каждый вектор-столбец записывают как транспонированную вектор-строку. Например, куб С₀ (11) записывают в виде:

	1	2	3	4	5	6	7	8	9
C0 =	[~	~	~	~	~	~	~	~	1]^T.	(16)

Тоже самое относится и к конкатенациям K₁, K₂, K₃. Тогда Пересечение C₀ Ç K₃ принимает вид:

	1	2	3	4	5	6	7	8	9	7	8	9	7	8	9	7	8	9
C0 =	[~	~	~	~	~	~	~	~	1	~	~	1	~	~	1	~	~	1]^T
K3 =	[~	~	~	~	~	~	0	0	0	0	1	1	1	0	1	1	1	0]^T	(17)
Ç	--	--	--	--	--	--	--	--	--	--	--	--	--	--	--	--	--	--
C1 =	[~	~	~	~	~	~	0	0	Æ	0	1	1	1	0	1	1	1	Æ]^T

Выражение (17) в значительной степени похоже на (15). Однако оно существенно отличается от него, так как пересечение в каждой координате выполняется с помощью матрицы Рота ¾ матрица U^†_R. Все пересечения в каждой координате выполняются в виде одного квантового блока QB_j, который реализует матрицу U_RБ-Д,n. Это значительно экономит объём аппаратуры, требуемый для выполнения пересечения C₀ Ç K₃ при использовании QD-алгоритма, тогда как время Dt₁ остаётся равным 1 вдеп. Таким образом, куб С₀, записанный в виде вектор-столбца в одном куните, пересекается с конкатенацией K₃, рассматриваемой в качестве куба и записанной как вектор-столбец в другом куните, и при этом = 1. Здесь ¾ число блоков QB_j. Теперь можно выполнить операцию фильтрации и пролифирации, учитывая одно из правил D-исчисления. Это правило гласит: если в одной из координат куба появился символ Æ, то весь куб считается пустым и далее, если в результате выполнения процедуры фильтрации не получено ни одного непустого куба, то результат пересечения является пустым: C₀ Ç K₃ = Æ. Более подробно процедуры фильтрации и пролиферации изложены в [2-5]. Здесь же приведены результаты этих процедур в случае классического параллельно-последовательного D-алгоритма (18) и QD-алгоритма (19):

	1	2	3	4	5	6	7	8	9		1	2	3	4	5	6	7	8	9
C1,1 =	~	~	~	~	~	~	0	1	1	C1,2 =	~	~	~	~	~	~	1	0	1	(18)

. .

	1	2	3	4	5	6	7	8	9		1	2	3	4	5	6	7	8	9
C1,1=	[~	~	~	~	~	~	0	1	1]^T	C1,2 =	~	~	~	~	~	~	1	0	1]^T	(19)

В случае классического параллельно-последовательного D-алгоритма и в случае QD-алгоритма будут получены 2 ку-ба: C_1,1 (18) и C_1,2 (19). По сути, были получены сходные результаты в виде кубов C_1,1 и C_1,2 . Однако в классическом случае (18) кубы C_1,1 и C_1,2 записаны как обычная вектор-строка. В квантовом случае (19) кубы C_1,1 и C_1,2 записаны в виде вектор-столбцов (точнее, в виде транспонированных вектор-строк). Теперь эти кубы следует записать в соответствующей форме, так чтобы их было удобно пересечь со следующей конкатенацией K₂ (K_r = K₂) — см. далее. Кубы C_1,1 и C_1,2 служат теми кубами, с которыми будет произведено пересечение с конкатенацией K₂ на следующем шаге (q = 2) QD-алгоритма (теперь уже можно не показывать сходное пересечение на втором шаге классического параллельно-последовательного D-алгоритма).

Второй шаг QD-алгоритма (шаг q = 2). На данном шаге производится одновременное пересечение двух кубов C_1,1 и C_1,2 с конкатенацией K₂, представленной в качестве куба и записанной в форме вектор-столбца (транспонированной вектор-строки) . Оба куба C_1,1 и C_1,2 записаны в одном куните. В другом куните записаны две конкатенации K₂. Блок QB_j реализует блочно-диагональную матрицу для параллельного выполнения двух пересечения: C_1,1 Ç K₂ и C_1,2 Ç K₂ . Пересечение C_1,1 Ç K₂ можно представить в следующем виде:

	1	2	3	5	7	3	5	7	3	5	7	3	5	7	4	6	8	4	6	8	4	6	8	4	6	8	9
C1,1=	[~	~	~	~	0	~	~	0	~	~	0	~	~	0	~	~	1	~	~	1	~	~	1	~	~	1	1]^T
K2=	[~	~	0	0	1	0	1	1	1	0	1	1	1	0	0	0	1	0	1	1	1	0	1	1	1	0	~]^T
Ç	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–
C2,1=	[~	~	0	0	Æ	0	1	Æ	1	0	Æ	1	1	0	0	0	1	0	1	1	1	0	1	1	1	Æ	1]^T

Пересечение C_1,2 Ç K₂ можно представить в следующем виде:

	1	2	3	5	7	3	5	7	3	5	7	3	5	7	4	6	8	4	6	8	4	6	8	4	6	8	9
C1,2 =	[~	~	~	~	1	~	~	1	~	~	1	~	~	1	~	~	0	~	~	0	~	~	0	~	~	0	1]^T
K2=	[~	~	0	0	1	0	1	1	1	0	1	1	1	0	0	0	1	0	1	1	1	0	1	1	1	0	~]^T
Ç	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–
C2,2 =	[~	~	0	0	1	0	1	1	1	0	1	1	1	Æ	0	0	Æ	0	1	Æ	1	0	Æ	1	1	0	1]^T

Оба пересечения выполняются параллельно (т.е. одновременно). После выполнения процедуры фильтрации и пролиферации мы, как и в случае классического параллельно-последовательного D-алгоритма [3], получим следующие 6 непустых кубов (классическая форма записи):

	1	2	3	4	5	6	7	8	9		1 1	2	3	4	5	6	7	8	9
C2,1,1=	~	~	1	0	1	0	0	1	1	C2,1,2=	~	~	1	0	1	1	0	1	1
	1	2	3	4	5	6	7	8	9		1	2	3	4	5	6	7	8	9
C2,1,3=	~	~	1	1	1	0	0	1	1	C2,2,,1=	~	~	0	1	0	1	1	0	1
	1	2	3	4	5	6	7	8	9		1	2	3	4	5	6	7	8	9
C2,2,2=	~	~	0	1	1	1	1	0	1	C2,2,3=	~	~	1	1	0	1	1	0	1

Для выполнения этих операций понадобились два кунита k_1,1 и k_2,1 (размерность их гильбертова пространства dim H_1,1 = dim H _2,1 = n = 54). Первый кунит k_1,1 относится к регистру QR₁, второй кунит k_2,1 ¾ к регистру QR₂. Понадобился и один интегрированный квантовый блок QB_j. Такой блок QB_j реализует блочно-диагональную унитарную матрицу U^†_RБ-Д,n = U^†_RБ-Д,54, построенную из 54 элементарных матриц U^†_R. Время выполнения первого шага Dt₂ = 1 вдеп. Здесь величина вдеп учитывает накладные расходы, связанные с временем выполнения процедур фильтрации и пролиферации.

Шаг 3. (шаг q = 3). На третьем шаге осуществляется одновременное пересечение шести полученных на предыдущем шаге кубов и конкатенации K₁ – см. (13) выше:
(C_2,1,1 Ç K₁), (C_2,1,2 Ç K₁), (C_2,1,3 Ç K₁); (C_2,2,1 Ç K₁), (C_2,2,2 Ç K₁), (C_2,2,3 Ç K₁). (20)

Подчеркнём, что все 6 кубов записываются соответствующим образом так, чтобы все пересечения (20) в соответствии с конкатенацией K₁ были удобными и наглядными.

	1	3	4	1	3	4	2	5	6	2	5	6	7	8	9
C2,1,1 =	[~	1	0	~	1	0	~	1	0	~	1	0	0	1	1]^T
K1 =	[0	0	0	1	1	1	0	0	0	1	1	1	~	~	~]^T
Ç	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–
C3,1,1=	[0	Æ	0	1	1	Æ	0	Æ	0	1	1	Æ	0	1	1]^T

^{. .}

	1	3	4	1	3	4	2	5	6	2	5	6	7	8	9
C2,1,2 =	[~	1	0	~	1	0	~	1	0	~	1	0	0	1	1]^T
K1 =	[0	0	0	1	1	1	0	0	0	1	1	1	~	~	~]^T
Ç	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–
C3,1,2=	[0	Æ	0	1	1	Æ	0	Æ	0	1	1	Æ	0	1	1]^T

^{. .}

	1	3	4	1	3	4	2	5	6	2	5	6	7	8	9
C2,1,3 =	[~	0	1	~	0	1	~	1	1	~	1	1	0	1	1]^T
K1 =	[0	0	0	1	1	1	0	0	0	1	1	1	~	~	~]^T
Ç	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–
C3,1,3 =	[0	0	Æ	1	Æ	1	0	Æ	Æ	1	1	1	0	1	1]^T

^{. .}

	1	3	4	1	3	4	2	5	6	1	3	6	7	8	9
C2,2,1 =	[~	0	1	~	0	1	~	0	1	~	0	1	0	1	1]^T
K1 =	[0	0	0	1	1	1	0	0	0	1	1	1	~	~	~]^T
Ç	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–
C3,2,1=	[0	0	Æ	1	Æ	1	0	0	Æ	1	Æ	1	0	1	1]^T

^{. .}

	1	3	4	1	3	4	2	5	6	2	5	6	7	8	9
C2,2,2 =	[~	0	1	~	0	1	~	1	1	~	1	1	0	1	1]^T
K1 =	[0	0	0	1	1	1	0	0	0	1	1	1	~	~	~]^T
Ç	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–
C3,2,2 =	[0	0	Æ	1	Æ	1	0	Æ	Æ	1	1	1	0	1	1]^T

^{. .}

	1	3	4	1	3	4	2	5	6	2	5	6	7	8	9
C2,2,3 =	[~	0	1	~	0	1	~	1	1	~	1	1	0	1	1]^T
K1 =	[0	0	0	1	1	1	0	0	0	1	1	1	~	~	~]^T
Ç	–	–	–	–	–	–	–	–	–	–	–	–	–	–	–
C3,2,3 =	[0	0	Æ	1	Æ	1	0	Æ	Æ	1	1	1	0	1	1]^T

После выполнения процедуры фильтрации мы не получим ни одного непустого куба, т.е. все полученные кубы пусты, так как содержат символ Æ, по крайней мере, в одной координате. Для выполнения параллельных пересечений необходимо два кунита k_1,1 и k_2,1 (dim H _1,1 = dim H _2,1 = n = 90). Первый кунит k_1,1 относится к регистру QR₁, второй кунит k_2,1 ¾ к регистру QR₂. Здесь, на третьем шаге размерность гильбертова пространства кунитов k_1,1 и k_2,1 n = 90 максимальна. Следовательно, если кунит КвУ содержит 100 значений: dim H _1,m = 100, то подобной размерности вполне достаточно, для решения поставленной задачи в данном примере[2]. Кроме двух кунитов на третьем шаге понадобится и один интегрированный квантовый блок QB_j. Такой блок QB_j реализует блочно-диагональную матрицу U^†_RБ-Д,n = U^†_{RБ-Д, 90}, построенную из 90 элементарных матриц Рота ¾ матриц U^†_R. Время выполнения третьего шага Dt₃ = 1 вдеп. Здесь величина вдеп учитывает накладные расходы, связанные с временем выполнения процедур фильтрации. Таким образом, общее время Dt = 3 вдеп. Следовательно, при использовании такой вычислительной модели как квантовый ИГТ задача автоматического доказательства теорем может быть решена с полиномиальным временем, полиномиальной пространственной сложностью и полиномиальным числом квантовых блоков QB_j.

Здесь для проверки уместно привести ещё один вариант метода грубой силы. Теорема Де Моргана и её доказательство выбрано не случайно. Оно сводится к простейшему логическому уравнению от двух независимых переменных x₁ и x₂ (n = 2). Например, для уравнения (7) в первой части работы может быть использован QD-алгоритм, который решает прямую задачу для всех наборов Dom f(x₁, x₂) (Dom f(x₁, x₂) = {á00ñ, á01ñ, á10ñ, á11ñ}). Если для всех четырёх наборов á00ñ, á01ñ, á10ñ, á11ñ, решение уравнения (7) даст значения 0, то уравнение (7) не имеет решения и тезис теоремы де Моргана в первой части работы будет доказан. Учитывая ограничения на объём статьи, мы не будет приводить пример решения нашей задачи в такой постановке и с использованием QD-алгоритма, а просто проиллюстрируем идею решения «вручную» для уравнения (7). Сначала выберем набор X₁ = á00ñ. Тогда

== =0.

Для набора X₂ = á01ñ имеем: == =0.

Для набора X₃ = á10ñ: = = =0.

Для набора X₄ = á11ñ: == =0.

Ни на одном наборе из Dom f(x₁, x₂) уравнение (7) не выполняется. Следовательно,

И теорема де Моргана доказана.

Заключение и выводы

Алгоритмы, в частности, D-алгоритмы, выполняющие полный и упорядоченный перебор в процессе доказательства теорем, требуют от классических компьютеров и классических ускорителей больших вычислительных ресурсов. В качестве таких ресурсов выступают большие интервалы Dt времени решения, большие объёмы ОП и большое число элементарных вычислительных модулей ¾ блоков B_j. Блоки B_j необходимы для одновременного (параллельного) выполнения многих операций пересечения ¾ операций a_g. Такие ресурсы при приемлемых физических размерах компьютера или процессора-ускорителя, «заточенного» под выполнение D-алгоритмов, могут предоставить только КвУ. Поэтому не случайно многие специалисты считают, что квантовые вычисления могут стать ведущим способом вычислений в XXI веке. Они придут на смену традиционным вычислениям на классических компьютерах. Не случайно Российский научный фонд (РНФ) впервые выделил 8 приоритетных направлений развития отечественной науки. Одно из них называется: «Разработка перспективных квантовых коммуникаций и квантовые вычисления».
Классические компьютеры и классические ускорители могут решать NP-полные задачи с линейно растущим интервалом времени: Dt = Pr = R ¾ см. (8) в первой части. Однако при этом экспоненциально растут пространственная сложность и требуемое число элементарных вычислительных модулей, т.е. число классических блоков пересечения ¾ блоков B_j.

В настоящее время КК в основном строятся на кубитах, хотя некоторые исследовательские группы разработали регистр КК на кутритах и даже на куквадритах. Для того, чтобы КК развивались наравне с классическими и для них выполнялся известный закон Мура, необходимо, к регистру КК каждые два года добавлять один кубит. Это так называемое квантовое следствие закона Мура. На самом деле КК развиваются быстрее. Подтверждающим примером могут служить последние разработки КК канадской компании D-Wave systems ¾ см. табл. 7. Исходя из табл. 7, регистр КК D-wave II может содержать 2⁵¹² различных 512-разрядных двоичных чисел. Это очень большой объём памяти. Сравним этот объём с объёмом ОП такого суперкомпьютера, как суперкомпьютер Sequoia (корпорация IBM), который в начале 2012 г. занимал первое место в TOP500. Объём ОП кластера Sequoia, равен 1.6 ПБ или 1,6´10¹⁵ байт. Отсюда объём его ОП во много раз уступает объёму памяти квантового регистра D-wave II: 8,5´10^{155 :} 1,6´10¹⁵ » 5,31´10¹⁴⁰ . Сравнивать с регистром КК D-wave 2X уже не имеет смысла (2¹⁰⁰⁰).

Таблица 7
Квантовые компьютеры компании D-wave systems
Наименование КК	Число n кубитов квантового регистра	Дата презентации
ORION	16	13.02.2007
LEDA	28	7.11.2008
D-wave I (D-wave One)	128	11.05.2011
D-wave II (D-wave Two)	512	2013 (май)
D-wave 2X	1000+	2015

Здесь целесообразно упомянуть и о некоторых прогнозах. Так, один из разработчиков КК D-wave I Дж. Роуз (Geordie Rose) в мае 2011 г. высказал прогноз о развитии КК. В нём он утверждал, что через 10 лет (т.е. в 2021) будет построен КК, у которого регистр будет содержать 1 млн. кубитов. Тогда же в интервью он добавил: «Если вы построите обычный суперкомп размером с Луну, то и тогда он не достигнет его производительности». Следует подчеркнуть, что многие математики и специалисты в области computer science не будут разочарованы, если регистр КК или КвУ в 2021 г. будет содержать 10000 кубитов. Следует, однако, подчеркнуть, что многие физики не считают КК компании D-wave systems полноценными (полномасштабными) КК. Часто их называют ограниченными или не универсальными КК, предназначенными для решения лишь определённого класса задач. Здесь же необходимо сказать о том, что корпорация IBM планирует с 2014 г. до 2019 г. потратить $3 млрд. на создание собственного КК. Корпорация HP также планирует разработать КК с 2014 г. до 2019 г., израсходовав на это в течении 5 лет $2,5 млрд.

Учитывая огромные инвестиции в квантовое железо, в наше время создаются всё новые и новые квантовые алгоритмы ¾ математическое обеспечение для КК. Квантовые алгоритмы, предугадывая практически неограниченную мощность КК, могут прийти на помощь математикам, физикам и специалистам других отраслей науки, чью работу нельзя представить без тех или иных видов доказательств. Подчеркнём, что современные математические доказательства теорем становятся всё сложнее и сложнее. Доказательства из явлений индивидуального опыта постепенно становятся явлениями опыта коллективного. Само понятие убедительности, тесно связанное с доказательством, начинает терять свой индивидуализированный оттенок[3] и все больше приобретает характер «коллективной убедительности». Иными словами, доказательство становится убедительным не для отдельного математика, а для некоторого научного коллектива. Например, один человек может проверить одну часть доказательства. Но эта часть опирается на утверждения, доказательства которых ему неизвестны. Но эти последние известны другим его коллегам. Тогда он вынужденно верит им в том, что эти доказательства правильны. Смысл коллективной убедительности заключается в том, что для каждой составной части доказательства найдется свой «отвечающий за неё» член коллектива. Для него непосредственно убедительна именно эта часть, а другие участники полагаются на него в данном вопросе (более детально см. [6]). Непревзойдённый пример такого доказательства — теорема о классификации конечных простых групп [7]. Хотя отдельные небольшие кусочки этого доказательства несложно проверить квалифицированному алгебраисту, похоже, что полностью его понимают только его авторы. Однако приходится верить, а иногда и пользоваться этим результатом, чтобы двигать математические исследования дальше.

Важно также и то, что в наше время представления о доказательствах изменяются ещё и под влиянием вычислительной техники. Теперь мы умеем производить на свет доказательства, которые требуют перебора столь большого числа вариантов, что этот перебор становится недоступным человеку. Но он доступен классическому компьютеру и, уж конечно, КК. Первым примером такого доказательства, когда использовался классический компьютер, стало решение знаменитой проблемы четырёх красок [8 ]. Учитывая это, можно предположить и сделать вывод, что в будущем нас ожидают доказательства сложнейших теорем с помощью КК и КвУ. Это значит, что проблема разрешимости (полуразрешимости) некоторых, в том числе и неразрешимых задач станет существенно яснее.

Литература

1. Пономаренко В.П. Теллурид кадмия-ртути и новое поколение приборов инфракрасной фотоэлектроники // Успехи физических наук, 2003. Т. 173, № 6 (июнь). С. 649-665.

2. Roth J.P. Diagnosis of automata failures: a calculus and method. // IBM Journal of Research and Development. 1966. № 7 (July). P. 18-32.

3. Правильщиков П.А. Закон сохранения перебора и естественный параллелизм D-алгоритмов для построения тестов и моделирования в технической диагностике. // Автоматика и телемеханика. 2004. № 7. Стр. 156-199.

4. Правильщиков П.А. Квантовый параллелизм и новая модель вычислений. / Труды 12-го Всеросийского совещания по проблемам управления - ВСПУ-2014. М.: Институт проблем управления им. Трапезникова РАН. 2014. 9616 с. Стр. 7319-7334. ISBN 978-5-91450-151-5. № госрегистрации: 0321401153.

5. Правильщиков П.А. Квантовый параллелизм и решение уравнений в задачах управления на базе новой модели вычислений // Труды 12-го Всеросийского совещания по проблемам управления ¾ ВСПУ-12. М.: Институт проблем управления им. Трапезникова РАН. 2014. 9616 с. Стр. 7335-7351. ISBN 978-5-91450-151-5. № госрегистрации: 0321401153.

6. Правильщиков П.А. Доказательство теорем с помощью квантового генератора тестов. // Информационные технологии в проектировании и производстве. 2015. № 3. С. 77-87.

7. Gorenstein D., Lyons R., Solomon R. The Classification of the Finite Simple Groups. AMS, 1994. URL: http://www.ams.org/online_bks/surv401/

8. Appel K., Haken W., Koch J. Every Planar map is Four Colorable // Illinois Journal of Mathematics. 1977. Vol. 21. P. 439-567.

---

[1] Данный доклад является продолжением первого доклада автора: Правильщиков П.А. Проблема алгоритмической разрешимости и полуразрешимости формальных систем и её решение с использованием квантового генератора тестов. Первый доклад также сделан на этой же конференции CAD/CAM/PDM-2015. Нумерация формул и рисунков продолжает ту, которая была в первом докладе.

[2] Повторим, что в настоящее время известный американский физик Д. Авшалом считает, что практически достижимым является значение n равное нескольким миллиона ¾ k×10⁶.

[3] Известно, например, такое определение доказательства: «доказательство есть некоторое рассуждение, которое убеждает меня настолько, что с его помощью я оказываюсь способным убеждать других».