Полезно ли использование компьютерной науки «игнорирования констант» при сравнении классических вычислений с квантовыми вычислениями?

Даниэль Санк упомянул в комментарии , отвечая на (мое) мнение, что постоянное ускорение для задачи, допускающей алгоритм полиномиального времени, скудно, что$10^8$

Теория сложности слишком одержима бесконечными пределами масштабирования. В реальной жизни важно то, как быстро вы получите ответ на свою проблему.

В компьютерных науках часто игнорируют константы в алгоритмах, и в целом это работает довольно хорошо. (Я имею в виду, есть хорошие и практические алгоритмы. Я надеюсь , что вы будете предоставлять мне (теоретические) алгоритмы исследователи имели довольно большую руку в этом!)

Но я понимаю, что это немного другая ситуация, как сейчас мы:

1. Не сравнивая два алгоритма, работающих на одном компьютере, но два (немного) разных алгоритма на двух очень разных компьютерах.
2. Сейчас мы работаем с квантовыми компьютерами, для которых, возможно, традиционных измерений производительности может быть недостаточно.

В частности, методы анализа алгоритмов - это просто методы . Я думаю, что радикально новые вычислительные методы требуют критического обзора наших текущих методов оценки производительности!

Итак, мой вопрос:

Сравнивает ли производительность алгоритмов на квантовом компьютере с алгоритмами на классическом компьютере, является ли практика «игнорирования» констант хорошей практикой?

Распространенное использование Computer Science «игнорирования констант» полезно только тогда, когда различия в производительности различных типов аппаратной архитектуры или программного обеспечения могут быть проигнорированы с помощью небольшого массирования. Но даже в классических вычислениях важно знать о влиянии архитектуры (поведение кэширования, использование жесткого диска), если вы хотите решить сложные проблемы или большие проблемы.

Практика игнорирования констант не является практикой, которая мотивирована (в смысле постоянного подтверждения) с точки зрения реализации. Это обусловлено главным образом интересом к подходу к изучению алгоритмов, который хорошо себя ведет в композиции и допускает простые характеристики, близкие к чистой математике. Теоремы ускорения для машин Тьюринга означали, что любое разумное определение не могло бы попытаться определить сложность задач слишком точно, чтобы прийти к разумной теории; и кроме того, в борьбе за поиск хороших алгоритмов для сложных задач постоянные факторы не были математически интересной частью ...

Этот более абстрактный подход к изучению алгоритмов был и остается в значительной степени плодотворным. Но теперь мы сталкиваемся с ситуацией, когда у нас есть две модели вычислений, где

• Один находится в продвинутом состоянии технологической зрелости (классические вычисления); и
• Один находится в очень незрелом состоянии, но пытается реализовать теоретическую модель, которая может привести к значительным асимптотическим улучшениям (квантовые вычисления).

В этом случае мы можем спросить, имеет ли смысл даже рассматривать асимптотическую выгоду с тщательным учетом постоянных факторов или без такового. Из-за дополнительных усилий, которые могут потребоваться для выполнения масштабируемых квантовых вычислений, не только скалярные факторы, но и полиномиальные «ускорения» в теоретической производительности могут быть вымыты после того, как все затраты на реализацию квантового алгоритма будут приняты во внимание.

В эти первые дни, также могут быть значительные различия в производительности для разных подходов к квантовой архитектуре. Это может сделать выбор архитектуры столь же важным (если не более важным) для того, насколько хорошо алгоритм работает, чем для асимптотического анализа - точно так же, как для вас будет иметь большое значение, выполняете ли вы свои обычные вычисления на машине фон Неймана или в сильно распределенной сети со значительными задержками.

Действительно важная вещь для практических вычислений - и всегда была - не только алгоритмы, но и реализация алгоритмов : алгоритм, реализованный определенным образом, на определенной архитектуре. Обычная практика асимптотического анализа, которая игнорирует постоянные факторы, позволяет нам обращать внимание на систематические, математические причины различий в производительности алгоритмов и практически мотивирована в тех случаях, когда архитектурные различия не настолько велики, чтобы доминировать в практической производительности. ,

Что касается квантовых технологий, мы не находимся в той счастливой ситуации, когда мы можем безопасно скрывать постоянные факторы в любом практическом контексте. Но, возможно, однажды мы сможем это сделать. Это долгая игра в квантовые информационные технологии - до сих пор почти единственная игра, в которую когда-либо играли академические компьютерные ученые, в том, что касается квантовых информационных технологий. В преддверии того дня, когда квантовая технология найдет свое начало, нам будет полезно продолжить асимптотический анализ в качестве одного из направлений исследования квантовых алгоритмов.

$O\left(f\left[N\right]\right)$$N$

$10^{10}$

$\approx300$

Вы не можете игнорировать постоянные факторы при сравнении квантовых вычислений с классическими вычислениями. Они слишком большие.

Например, вот изображение с некоторых слайдов, которые я представил в прошлом году:

Вещи внизу - магические фабрики. Они занимают 150 тыс. Кубитов. Поскольку логический элемент AND использует 150K-кубиты в течение 0,6 миллисекунды, мы предполагаем, что объемно-временной объем квантового логического элемента AND составляет порядка 90 кубит-секунд.

Одна из целей моих коллег - использовать 1 процессор на 100 кубитов при выполнении исправления ошибок. Таким образом, мы могли бы сказать, что 90 кубит-секунд требуют 0,9 секунды процессора. Мы сделали квантовые конструкции в несколько раз более эффективными с тех пор, как было сделано вышеупомянутое изображение, поэтому вместо этого назовем его 0,1 cpu секунд.

(Есть много предположений, которые входят в эти оценки. Какая архитектура, частота ошибок и т. Д. Я только пытаюсь передать идею порядка величины.)

Для выполнения 64-битного сложения требуется 63 логических элемента. 63 * 0,1 секунды процессора ~ = 6 секунд процессора. В количественном отношении 64-битное сложение стоит больше, чем секунда процессора. Классически 64-битное сложение обходится дешевле, чем наносекунда процессора. Здесь легко найти постоянную разницу в 10 миллиардов. Если сравнить с параллельной классической машиной, такой как графический процессор, цифры станут еще хуже. Вы не можете игнорировать постоянные факторы с таким количеством цифр.

Например, рассмотрим алгоритм Гровера, который позволяет нам искать удовлетворительные входные данные для функции в sqrt (N) оценках функции вместо N оценок. Добавьте постоянный коэффициент 10 миллиардов и определите, где квантовый компьютер требует меньше оценок:

Алгоритм Гровера не может распараллеливать оценки, а для оценки требуется как минимум один логический элемент И, поэтому в основном вы получаете выгоду от использования ЦП только тогда, когда поиск занимает десятки миллионов лет.

Если мы не улучшим постоянные факторы, никто никогда не будет использовать поиск Гровера для чего-нибудь полезного. Прямо сейчас квантово-классическая ситуация - экспоненциальное преимущество или спад.

В то время как другие ответы дают хорошие моменты, я чувствую, что все еще немного не согласен. Итак, я поделюсь своими мыслями по этому вопросу.

Короче говоря, я думаю, что постоянное «как есть» - это в лучшем случае упущенная возможность. Возможно, это лучшее, что мы можем получить на данный момент, но это далеко от идеала.

Но сначала я думаю, что короткая экскурсия не обязательна.

Когда у нас есть эффективный алгоритм?

Когда Даниэль Санк спросил меня, что я буду делать, если бы существовал алгоритм для вычисления простых чисел с помощью $10^6$Фактор ускорения на тестовом наборе серьезных случаев, я сначала ответил, что сомневаюсь, что это будет связано с алгоритмическими улучшениями, но с другими факторами (или машиной, или реализацией). Но я думаю, что у меня другой ответ сейчас. Позвольте мне дать вам тривиальный алгоритм, который может учитывать очень большие числа в течение миллисекунд и тем не менее очень неэффективный :

1. Взять набор $P$ из (довольно больших) простых чисел.
2. вычисление $P^2$множество всех композитов с двумя факторами из $P$, Для каждого композита сохраните, какая пара простых чисел используется для его построения.
3. Теперь, когда дан экземпляр из $P^2$Просто посмотрите на факторизацию в нашей таблице и сообщите об этом. В противном случае сообщить об ошибке

Я надеюсь, что очевидно, что этот алгоритм является мусором, так как он работает только правильно, когда наш вход в $P^2$, Тем не менее, можем ли мы увидеть это, когда алгоритм представлен в виде черного ящика и «по совпадению» только тест с входными данными из$P$? Конечно, мы можем попробовать протестировать множество примеров, но это очень легко сделать$P$ очень большой без алгоритма, неэффективного на входах от $P^2$ (возможно, мы хотим использовать хэш-карту или что-то в этом роде).

Таким образом, не исключено, что наш алгоритм мусора, по совпадению, может показаться «чудесным» ускорением. Теперь, конечно, есть много методов проектирования экспериментов, которые могут снизить риск, но, возможно, более хитрые «быстрые» алгоритмы, которые все еще не работают во многих, но недостаточно примеров, могут обмануть нас! (также обратите внимание, что я предполагаю, что ни один исследователь не является злым , что усугубляет ситуацию!)

Итак, я бы сейчас ответил: «Разбудите меня, когда появится лучший показатель производительности».

Как мы можем сделать лучше, тогда?

Если мы можем позволить протестировать наш алгоритм «черного ящика» во всех случаях, мы не можем быть обмануты вышеизложенным. Однако это невозможно для практических ситуаций. (Это можно сделать в теоретических моделях!)

Вместо этого мы можем создать статистическую гипотезу для некоторого параметризованного времени выполнения (обычно для входного размера), чтобы проверить это, возможно адаптировать нашу гипотезу и протестировать снова, пока мы не получим гипотезу, которая нам нравится, и отклонение нулевого значения не кажется разумным. (Обратите внимание, что, вероятно, есть и другие факторы, которые я игнорирую. Я практически математик. Дизайн эксперимента не входит в мои компетенции)

Преимущество статистического тестирования на параметризацию (например, наш алгоритм $O(n^3)$? ) является то, что модель является более общей и, следовательно, ее «обмануть» сложнее, чем в предыдущем разделе. Это не невозможно, но, по крайней мере, статистические утверждения о том, является ли это обоснованным, могут быть оправданы.

Итак, что делать с константами?

Думаю только констатирую$10^9$ Ускорение, вау! »- плохой способ разобраться с этим делом. Но я также считаю, что игнорирование этого результата также плохо.

Я думаю, что наиболее полезно рассматривать любопытную константу как аномалию , т.е. это утверждение само по себе требует дальнейшего изучения. Я думаю, что создание гипотез, основанных на более общих моделях, чем просто «наш алгоритм требует X времени», является хорошим инструментом для этого. Так что, хотя я не думаю, что мы можем просто взять на себя соглашения CS здесь, полностью игнорировать «презрение» к константам - тоже плохая идея.