Поскольку ответа не было дано, был установлен флаг с просьбой преобразовать этот вопрос в вики сообщества.
Комментарии Аарона Стерлинга, Сашо Николова и Вора были объединены в следующую резолюцию, которая открыта для обсуждения в вики сообщества:
Решено: Что касается классических алгоритмов, которые выводят числа, выборки или траектории моделирования, строгая математическая логика требует, чтобы были приняты либо все четыре из следующих предложений, либо ни одно из них:
- Мы можем исключить классический алгоритм за полиномиальное время для генерации случайных чисел. [1]
- «Мы можем исключить классический алгоритм за полиномиальное время для выборки выходного распределения квантового компьютера при единственном предположении, что полиномиальная иерархия бесконечна». [2]
- «Мы не можем моделировать [квантово-механическую траекторию] обычным образом ... слишком много переменных. " [3]
- Расширенный тезис Черча-Тьюринга (ECT) исключен по строгой причине, что классические алгоритмы не могут генерировать случайные числа. [4]
Чтобы начать обсуждение, здесь приводятся положительные и отрицательные ответы, которые, хотя и оправданы, намеренно завышены. Сильно утвердительный аргумент может быть:
Утверждение: эти четыре утверждения отражают теоремы, которые для соблюдения строгости требуют, чтобы мы никогда не говорили о классических алгоритмах, которые генерируют случайные числа, случайные выборки или квантовые симуляции, а скорее говорили только о классических алгоритмах, которые генерируют псевдослучайные числа и расширение) псевдослучайные выборки и псевдоквантовое моделирование.
При этом все четыре утверждения верны. Более того, чтобы избежать двусмысленности и предотвратить путаницу, математики должны поощрять ученых и инженеров прикреплять префикс «псевдо» почти ко всем случаям «случайный», «выборочный» и «квантовое моделирование».
Сильно отрицательный аргумент может быть:
Негатив: эти утверждения (и связанные с ними формальные теоремы) являются знаковыми знаками, которые направляют нас в область математики в стиле Лакатоса «красный свет», где нас с энтузиазмом принимают (что можно назвать) дисциплины псевдослучайности псевдосэмплирование и псевдосимуляция ... математические практики, забавные по чрезвычайно греховной причине: они достигают математических эффектов, которые формальная логика считает невозможными. Следовательно, что может быть более волшебным и более забавным, чем этот вывод: каждое из четырех утверждений резолюции формально верно, но практически неверно?
При этом все четыре утверждения являются ложными. Более того, поскольку большинство практических аспектов «случайности», «выборки» и «квантового моделирования» происходят в этой магической среде, в которой вопросы, связанные со сложностью Колмогорова и оценками оракула, преднамеренно упускаются из виду, именно математики должны изменить их использование.
Реалистично, однако, как теоретики сложности должны формулировать свои выводы, касающиеся случайности, выборки и симуляции ... с одной стороны, с целью поддержания разумного баланса ясности, краткости и строгости ... и с другой стороны, с целью к поддержанию связи с низким уровнем шума с другими дисциплинами STEM? Последняя цель особенно важна, поскольку практические возможности постоянно растут в таких областях, как криптография, статистическое тестирование, машинное обучение и квантовое моделирование.
Было бы очень полезно (и тоже приятно) читать аргументированные ответы, положительные или отрицательные.
Заданный вопрос
Какова / является общепринятая роль (и) проверки в теоретико-сложных определениях, связанных с выборкой, моделированием и тестированием тезиса расширенной Церковью-Тьюринга (ДЭХ)?
Предпочтительный ответ - ссылки на статьи, монографии или учебники, в которых подробно обсуждаются эти вопросы.
Если эта литература окажется разреженной или иным образом неудовлетворительной, то (через два дня) я переведу этот вопрос в вики сообщества:
Какова / является разумной и правильной роль (и) верификации в теоретико-сложных определениях, связанных с отбором проб, моделированием и тестированием тезиса расширенной Церковью-Тьюринга (ДЭХ)?
Фон
Заданный вопрос мотивирован недавней веткой «Что бы значило опровергнуть тезис Черча-Тьюринга?» в частности, (превосходное ИМХО) ответы Джила Калаи и Тимоти Чоу
В заданном вопросе фраза «правильные и / или принятые теоретико-сложные определения» должна толковаться как сдерживающая Алису от неправдоподобных утверждений, подобных следующему:
Алиса: Вот мой экспериментальный образец действительно случайных двоичных цифр, вычисленных моей (однофотонной) линейной оптической сетью.
Боб: Вот мой смоделированный образец псевдослучайных цифр, вычисленных на классической машине Тьюринга.
Алиса: Извините, Боб ... ваш образец алгоритмически сжимаем, а мой нет. Поэтому мои экспериментальные данные показывают, что ДЭХ ложен! »
В отсутствие какой-либо связи проверки с выборкой аргументация Алисы безупречна. Другими словами, должны ли теоретики сложности считать ДЭХ уже формально опровергнутым… десятилетия назад?
С практической точки зрения методы моделирования, связанные с квантовой выборкой траекторий на пространствах сортовых состояний , широко используются во многих дисциплинах науки и техники. Вот почему теоретико-сложные определения выборки, которые учитывают центральную роль верификации (которая неотделима от воспроизводимости) в науке и технике, были бы очень полезны для практикующих ученых и инженеров ... особенно, если эти определения сопровождались теоремами, описывающими вычислительную сложность проверенная выборка.
Добавлено редактирование: благодаря сотрудничеству между Женевским университетом и компанией id Quantique , вполне реально выполнить это упражнение в реальности.
Вот 1024 случайных бита, которые сертифицированы id Quantique как алгоритмически несжимаемые:
0110001000010111111100010111001000101110110001001100000010010110
0101000110100011101001110110000001010110011101111110101010110100
1001001110001110101000001110000101000110000001010001101001000000
0110101010110000110101001110011010010101000000110000010000010111
0100110110001011011101110000010110000100110001001110011000000011
1111010100010110110010011000110110110010101101010000010010001111
1101111000111101111010000110100110011000101101010110110110000101
1110111100000111000111101111110011101101110111101001001111111110
1000001011001000011101001000001110101110101010000111100000111010
1010011001110111101001100010110000101101100100101100000110111111
1000001101111001111011100011110101011010010100000010100101100010
0011101000111100000001101100111110100100010100100010011000001000
0000001001110101010111110001010010000111010011000100001101101000
1011111010001000110101110101111101010111111011011111110010010111
0111000010000111000100110110010101110100000110101001111010101001
0100011110011101000011000100110110010000100001111100101001010011
Должны ли мы сейчас принять утверждение: «Тезис ДЭХ опровергнут»?
Если нет, то какие основания мы должны дать?
Ответы:
Суть вопроса в том, что, учитывая, что квантовая вероятность является источником истинной случайности, как это влияет на расширенный (или эффективный, или полиномиальный) тезис Черча-Тьюринга?
Ответ в том, что, по предположению, это не влияет на это. Люди предполагают, что BPP = P, то есть что рандомизированные алгоритмы могут быть дерандомизированы с помощью генераторов псевдослучайных чисел с полиномиальными издержками. Вера в PRNG как замену истинной случайности является одной из причин, по которой люди поверили бы в расширенный тезис Черча-Тьюринга, если бы не квантовые вычисления.
источник