Comments 83
Верна ли мысль. Что 5 кубитов это всевозможные комбинации чисел от 1 до 5
А 100 кубитов это всевозможные комбинации чисел от 1 до 100. Следовательно любой 100 кубитный компьютер взломает шифрование в 100 символов?
Спасибо
Где то в комментариях была мысль, что если создать 1 настоящий кубит, то можно на нём же сделать триллион виртуальных кубитов. Реально ли это или это фантазии?Предполагается, что имея триллионы настоящих кубитов, можно сделать несколько «логических», устойчивых к ошибкам.
Верна ли мысль. Что 5 кубитов это всевозможные комбинации чисел от 1 до 55 кубитов могут содержать все возможные значения от 0 до 31. 6 кубитов содержат все возможные значения от 0 до 63. Каждый дополнительный кубит удваивает число возможных значений.
Следовательно любой 100 кубитный компьютер взломает шифрование в 100 символов?1024-кубитный компьютер «взламывает» RSA-1024 быстрее, чем классический компьютер (но с КУЧЕЙ оговорок).
Эффективность симуляции vs эффективность реальных квантовых компьютеров.
Привожу простой пример из комментариев к моему посту.
«Тогда текущий рекорд симуляций — 49 кубит поставленный в прошлом году на крупнейшем китайском суперкомпьютере (Sunway TaihuLight): arxiv.org/abs/1804.04797» Mad__Max
При этом потребляемая мощность данного суперкомпьютера с охлаждением — 28 МВт, а стоимость — $273 млн.
Следующий квантовый компьютер IBM будет иметь уже около 50 кубитов. Цена, энергопотребление, размеры у него в разы или на порядок меньше. Да и вообще, можно ведь по облаку использовать машинки IBM, только когда в них есть потребность (похоже это главная часть бизнес-модели). Да, это всё ещё не идеальный КК, но его схема уже довольно близка к нему (как-нибудь покажу логическую схему связанности кубитов их новенького Q system One, она уже почти идеальная, хоть и двухмерная). И я уверен, что следующую итерацию после 50ти кубитного КК уже точно не будет смысла симулировать на каком-либо суперкомпьютере (да и 50ти кубитный почти наверняка будет экономически привлекательнее симуляции). А ждать этого придётся отнюдь не десятилетия, а всего десяток-другой месяцев.
Похоже в IBM всё же вынесли некую мудрость из ошибок и открытий прошлого века. В частности — выработали стратегию развития подрывных технологий и строительства бизнеса на них.
Через пару-тройку месяцев у меня будет очень хороший материал для всех, кто интересуется КК, но сомневается в том, что эта технология уже стучит в окошко. Подписывайтесь, что бы не пропустить!
И в целом, для каждой отдельной программы сложность симулятора надо обсчитывать заново. Грубо говоря, если у нас есть кубит, однозначно вычисляемый через значения других — его можно не добавлять в симуляцию, а вычислять «на лету». Если кубит в процессе вычислений больше не нужен — можно исключить его из симуляции.
Но да, лимит в 50 кубитов очень уж жесткий. Вряд ли кто будет заморачиваться такими оптимизациями. Разве что, аспирантов напрягут.
Если для 50 «идеальных» кубитов требуется суперкомпьютер, страшно представить, что будет, когда туда все алгоритмы регистрации и коррекции добавить.
Недавний прогноз, обсуждаемый в MIT Technology Review около месяца назад ссылался на электронный препринт How To Factor 2048 Bit RSA Integers In 8 Hours Using 20 Million Noisy Qubits и вызвал даже некий оптимизм, так как до этого были оценки с миллиардами и более. Но при этом, даже если принять обещание ИБМ об удвоении числа кубитов каждый год, то получится что с их 20 более-менее нормально работающими кубитами надо ждать 20 лет. Но возможно, Microsoft со своим Q# надеется на топологические кубиты и на то, что коррекция ошибок на них требует меньших издержек.
Забавно, но весь квантовый хайп идет от того, что математика квантмеха — это линейная алгебра на уровне первого курса.
Поэтому в один прекрасный день все, кому не лень, написали по своему "языку квантового программирования" (= библиотеке простеньких функций для перемножения матриц 2х2), и объявили себя участниками "квантовой гонки". После этого они набрали несколько вчерашних аспирантов для какого-никакого теоретического RnD, и начали безудержный пиар. Разумеется, суммы на пиар превышают затраты на RnD минимум на порядок.
Единственной компанией, которая попыталась сделать хоть что-то настоящее, остается IBM с ее Q Experience.
Ну в какой-то момент должно это пройти, думается… Когда станет ясно, что это дело еще многих-многих лет.
А IBM крутейшие, я немного игрался с их Qiskit — это прямо очень интересно, хотя я почти ничего не знаю (представляю, как здорово это для тех, кому актуально это по тематике).
А оно уже проходит.
Ибо в современном квантовом мире серьезный софт — это жесткие алгоритмы напополам с коррекцией ошибок, серьезное железо — это оптимизация паразитных эффектов на чипах (чуть ли не вплоть до их изотопического состава).
А хайперы третий год продолжают мычать что-то невнятное про "новый фреймворк" и "более лучшие кубиты", что выглядит более чем подозрительно даже для журналистов из желтой прессы. При этом свою главную задачу — автоматический синтез кода в зависимости от архитектуры чипа — они успешно запороли.
А Qiskit хорош, да. Там ничего особенного, но он добротно сделан, и его можно пощупать ручками на реальном железе.
Вообще, если есть понимание, как конвертируется обычный алгоритм в его квантовую версию, то таких вопросов быть не должно. То есть на обычных алгоритмах просто запускают задачу меньшей размерности, чем обеспечивают обход всех ветвей алгоритма, не требуя при этом перемалывать много данных.
Собственно для понимания процесса конверсии было бы прекрасно увидеть ещё одну статью в таком же стиле, как и представленная сегодня. Как я (по своей неграмотности) понимаю, алгоритмы в квантовые не конвертируются. То есть (упрощённо) нужны такие люди, которых очень-очень мало и при этом они ещё и очень-очень умные. Значит без таких людей квантовый компьютер — абсолютно бесполезная штуковина. А сами эти шаманы каким-то хитро-мудрым математическим аппаратом переводят уравнения квантовой физики в некую надежду на получение состояния квантовой системы, близкого к решению задачи при огромном количестве запусков. При этом — что там между задачей и готовым сбором статистики по результатам решения — никто не знает (ну кроме шаманов, понятно). В статье даже парочка шаманов упомянута — Гровер и Шор. Они, видимо, какую-то удачную конверсию относительно общего алгоритма сочинили? Типа факторизации.
И вот с таким представлением о алгоритмах квантовых компьютеров вы ещё получаете надежду на развитие, но в реальности у подавляющего большинства даже такого представления нет. Поэтому статья именно об алгоритмах очень нужна. Без неё — квантовый компьютер есть просто безумная идея, абсолютно недоступная для не знакомых с бездной формул из квантовой физики и ещё хрен знает откуда.
Отсюда вопрос: что мешает производить «автоматический синтез/оптимизацию квантовых алгоритмов» с использованием возможностей самих квантовых компьютеров по одновременному перебору вариантов? Конечно имеется ввиду не сейчас, а в перспективе, когда (если) будут решены текущие проблемы реальных КК (недостаточное число кубитов, ограничения по связанности между ними, шумы и проч.).
Так же мне представляется, что для синтеза/оптимизации квантовых алгоритмов на них самих, потребуется городить не самый компактный оракул из кучи C-U, CC-U и т.д., где к примеру контроллируемую операцию U мы вынуждены задавать не квантовой переменной, как хотелось бы, а константой, поскольку архитектура квантовых компьютеров пока не фон-Неймановского типа (конечно, что-то можно упрятать в функции/макросы или некое подобие микрокода, но ведь это лишь чисто визуально упростит исходный код, а при исполнении все равно развернется) :(
лучше Гровера… пока не придумали
Более того, доказывали что для поиска единицы функции (f(x)=1 при единственном x=x0) гровер оптимален — https://cds.cern.ch/record/339558/files/9711070.pdf "Grover’s quantum searching algorithm is optimal"
Длительность работы алг.гровера делает его полностью неприменимым на практике для интересных размеров (кв.комп перегреется гарантированно раньше чем будет проведено 2^(n/2) последовательных операций f(x) и f^(-1)(x) внутри гровер-алгоритма при n>128). На классических СБИС (CPU, GPU, FPGA) с параллелизмом вполне перебираются пространства размером 2^56 — 2^64 — How to break DES for 8,980€, 2006 (8 дней на 56 бит), 1 день 56 бит
Однако задачи синтеза (компиляции, планирования) схем, что классических СБИС, что квантовых — это не задача перебора, а задача оптимизации. (как и компиляция алгоритма в последовательность инструкций — gcc.) Для таких задач обычно не требуется найти самый оптимальный вариант размещения элементов, сойдет просто любой достаточно хороший, приблизительный способ. Например https://openreview.net/pdf?id=S1eEBO3nFE https://arxiv.org/pdf/1606.07413.pdf https://arxiv.org/pdf/1712.04722.pdf https://arxiv.org/pdf/1810.00129.pdf
PS ваш https://uwspace.uwaterloo.ca/bitstream/handle/10012/7818/Amy_Matthew.pdf сообщает "Complexity of T-count minimization… is NP-hard", и маловероятно что кв.комп приравняет классы BQP=NP.
кв.комп перегреется гарантированно— идеальный квантовый компьютер обратим и поэтому не греется вообще. Про неидеальный сложно что-то говорить, но по крайней мере для обратимых вычислений нет проблемы с принципом Ландауэра к которому современные системы, вроде, уже подошли почти вплотную.
Под "перегреется" я имел в виду декогеренцию.
Предположим, идеальный кв.комп. будет исполнять 1 операцию (один слой независимых операций) за 1 наносекунду (аналог тактовой частоты 1 ГГц; ibm qx на порядки медленнее). Какова глубина в вентилях реализаций функций des, aes, sha? (- десятки тысяч, 1512.04965) Сколько времени займет гровер-перебор 56-64 битного ключа; 128 битного; 256 битного? (- часы; более млн лет (??!); 10^26 лет при возрасте вселенной 10^10). Такие объемы вычислений даже на нынешних очень надежных кремниевых схемах будут давать сбои, а "Noisy Intermediate-Scale Quantum" (current and near-term systems of 1000 qubits or less) не зря названы шумными (кубитный вентиль на 10 порядков шумнее Si-логического) См. также https://en.wikipedia.org/wiki/Transcomputational_problem https://en.wikipedia.org/wiki/Limits_of_computation
Оценка длительности от более грамотных авторов — http://cs.brown.edu/courses/csci1800/sources/2018_NAE_QuantumComputing_ProgressAndProspects.pdf
(page 91) entire 128-bit key space of AES-GCM… assuming 100-nanosecond gate times and current algorithms for error correction, a single quantum computer would require more than 10^12 years to crack AES-GCM
Even if a computer existed that could run Grover’s algorithm to attack AES-GCM, the solution is quite simple: increase the key size of AES-GCM from 128-bit to 256-bit keys. Running Grover’s attack on a 256-bit key is effectively impossible, since it requires as many steps as a classical attack on a 128-bit key. Transitioning to a 256-bit key is very practical and can be put to use at any time. Hence, AES-GCM can be easily made secure against an attack based on Grover’s algorithm.
(92) A hash function that produces 256-bit outputs is not expected to be threatened by quantum computing. Even using Grover’s algorithm, it is currently believed to be essentially impossible (with a depth on the order of 2144 T gates on 2400 logical qubits) to break a hash function like SHA256
(93) Grover’s algorithm would be suited to solving a Bitcoin challenge. However, as the second to last row in Table 4.1 shows, the overhead of implementing Grover’s algorithm using physical qubits to solve the proof-of-work challenge is currently estimated to require well over 10 minutes… (94: SHA256 1.8 * 10^4 years)
Вывод — гровер представляет собой огромнейший теоретический прорыв; но он не меняет P?NP в теории сложности, и не является практически применимым (для 2^64 — 2^80 сравнимым по скорости, реализуемым и более дешевым является параллельный перебор на fpga).
Кремнию до лимита Ландауэра сравнительно далеко, я вроде бы встречал оценки 10 тысяч раз до лимита (http://large.stanford.edu/courses/2016/ph240/vega1/ http://www.microenergy2017.org/Slides_Anderson.pdf). Пересчитывать число транзисторов умноженное на частоту надо очень аккуратно, т.к. dark silicon / dim silicon (http://www.ndcl.ee.psu.edu/papers/SteepslopeIEEComp.pdf http://darksilicon.org/ и т.п.) — лишь небольшая доля от всех транзисторов переключается в данный такт.
Сколько до лимита Ландауэра осталось, действительно оценки разные, я когда-то смотрел, сейчас нашёл только прошлогоднюю статью Франка, который активно продвигает обратимые вычисления, где он говорит о десяти годах, правда как-то очень косвенно упоминая этот принцип, хотя в той-же википедии пишут о 2050 годе.
На каких размерах: длина аргумента + глубина перебираемой функции (плюс её обращение) по вашему гровер будет удачнее перебора на FPGA? Какого типа функция больше подойдет для такого ускорения? (Она должна быть достаточно короткой, и ответ на нее — достаточно ценным. В криптографии стоимость ответа иногда вполне оценивается.)
Классические переборы легко параллелятся на сотни-тысячи переборщиков в каждой FPGA или на каждой плате, и за линейное количество денег можно поставить сотни, тысячи, десятки тысяч чипов/плат. Частота перебора — сотня МГц. Т.е. за 1 млн долларов (цена 1 холодильника без кв.чипов) легко получить порядка миллиона переборщиков на 100 МГц ~ 10^(6+2+6)=10^14 = 2^46 в секунду. 2^62 в сутки.
С другой стороны я не понимаю как можно распараллеливать гровера (мне кажется, что никак).
Обратимость вычислений мне казалось лишь мешает ускорению операций.
Квантовый компьютер на 2^64 операций на 1 ГГц будет работать миллионы лет (для сколь-нибудь глубокой функции). В году 2^55 срабатываний на 1 ГГц, в сутках — 2^46, в секунде 2^30.
Когда ожидать реализаций кв.комп с временем существования более 1 миллисекунды и размером в тысячи логических (точных) кубитов? Из реальных машин по списку https://quantumcomputingreport.com/scorecards/qubit-quality/ таких нет (Table 1; кроме некоего "IonQ 11 Qubit" https://arxiv.org/pdf/1903.08181.pdf https://arxiv.org/pdf/1603.04512.pdf обещают 0.5 с прогнозом свыше 1000 сек). Работают реальные системы (обратимо) не на 1 ГГц, а медленнее 10 МГц (Table 3).
С другой стороны я не понимаю как можно распараллеливать гровераГровер работает на задачах прямого перебора, так что если у вас есть n квантовых компьютеров, то каждому передаётся своя часть задачи и вся задача решается в n раз быстрее. Такое распараллеливание, как и скорость работы вообще не рассматривается в оценках с O большое, они же специально делаются для возможности оценить сам алгоритм, а не железо.
Обратимость вычислений мне казалось лишь мешает ускорению операций.Я имею в виду, что обраттимые вычисления, как там Франк и другие пишут, просто позволяют повысить тактовую частоту (что, как уже написал, вообще не учитывается во всяких классах).
Когда ожидать реализаций кв.комп с временем существования более 1 миллисекунды и размером в тысячи логических (точных) кубитов?В зависимости от определения можно говорить и «уже давно» (ДНК — не по теме правда, если вспомнить определение логического кубита) или «вообще никогда» (точными они никогда не будут). На всякий случай, я про теорию только писал.
Как я понимаю — после разбития входной задачи для гровера на n подзадач в n-1 частей для всех x значение f(x)=0. Только в 1 части f(x)=1. Если у функции в данном участке нет единицы, внутри гровера не будет какой-то выделенной амплитуды для усиления, т.е. на этой части алгоритм не работает…
В вики что-то есть — https://en.wikipedia.org/wiki/Grover's_algorithm#Quantum_partial_search
https://cds.cern.ch/record/339558/files/9711070.pdf "… show that unfortunately quantum searching cannot be parallelized better than by assigning different parts of the search space to independent quantum computers"
https://eprint.iacr.org/2017/811.pdf
0.359msec to implement the AES-256 function
we derate these parameters by a factor of a million; giving us… T1 = 0.3nsec for AES (Both these speed estimates are approximately an order of magnitude faster than how fast we can implement these functions using conventional gates.)
У Франка про ГГц нашел только box 4 про наномеханику с тактовым входом. Однако "Operating frequencies on the order of a GHz should be possible" может относится не к тактовой частоте полной схемы, а к длительности срабатывания одного логического элемента (NAND gate? switching time of 10ns… away 18 GHz; 36: " logical NAND operation as the example… assumed that about 20,000 logical operations (LogOps) are required per FLOP… a switching speed of 0.1ns per NAND gate" — молодцы, внезапно в сто раз более быстрый гейт для получения GFLOPS/W и без учета обслуживающей логики; a frequency of f = 100 MHz). Одиночные транзисторы и лог.эл. в кремнии также имеют очень небольшую задержку, но на выходе почему-то получаются процессоры не быстрее 5 ГГц.
Тогда как реальная схема k-bit ALU или "FLOP" требует вполне известной глубины (например от 30 до 140 последовательно срабатывающих элементов — FO4 per stage is between 30 and and 140). И намного больше энергии (ресурсов) тратят не схемы alu/fma, а обеспечение их данными (energy per operation, pj)
Что думаете про "IonQ 11 Qubit"? Их ионно-ловушечный чип должен находиться в сверхвысоком вакууме, но я не понял, нужно ли его охлаждать до единиц кельвинов или ниже. (хм, "ultimate vacuum environment might require low-temperature operation (<10 K)… (~5 K) " и там же картинка всей установки).
В ProgressAndProspects про такой класс машин на стр 163
http://cs.brown.edu/courses/csci1800/sources/2018_NAE_QuantumComputing_ProgressAndProspects.pdf#page=163
Two technologies, one using trapped ionized atoms (trapped ions) and the other using miniature superconducting circuits, have advanced to the point where research groups are able to build small demonstration quantum computing systems
А для реально существующих «современных» компьютеров ( Benchmark system — представляющих в работе типовые для 2013-2015 годов компьютеры, с учетом даты публикации в 2016м году) до лимита необратимых вычислений еще больше 6 порядков остается. Ну сейчас наверно как раз около 6 порядков, с учетом роста эффективности в 2-3 раза достигнутого за последние несколько лет.
Так что еще десятки лет можно продолжать наращивать мощность и энергоэффективность классических систем работающих при «комнатных» температурах не слишком считаясь с ограничениями со стороны термодинамики.
quverty
Алгоритм Гровера в общем случае все же экспоненциально сложный, хоть и быстрее перебора.
Не хакать, а уменьшает сложность на корень.
Была сложность 2^256, стала 2^128 — примерно 10^39. Итого для решения за 30 лет одного хэша нам понадобится «всего» 10^30 операций в секунду. Для сравнения всю мощность компьютеров человечества можно грубо оценить сверху как — 10 миллиардов процев на 100 ГФлопс = 10^21 — «всего» в миллиард раз меньше.
Квантовые компьютеры не совершат никакого глобального переворота. Точка.
Квантовые компьютеры не совершат никакого глобального переворота. Точка.
Квантовые компьютеры, в общем случае, перевернут физику, химию, биологию, фармакологию и кучу смежных областей. К примеру, добывать новые лекарства будут совсем по-другому.
Я понятия не имею об этом. Но всем нужны квантовые симуляции огромных молекул для того, чтобы узнать как то или иное активное вещество взаимодействует с белками и прочим. Вот пример проблем для кв. компьютеров:
Во-первых, это изначально "сложные" молекулы, которые вообще непонятно как работают, типа этой
Во-вторых, статистическое исследование "параметрических пространств" (=молекул, сценариев, комбинаций условий): когда каждый из 20 радикалов может быть ориентирован двумя разными способами, необходим миллион отдельных симуляций одного и того же процесса. Квантовому компьютеру достаточна одна симуляция на "20 копиях" молекулы/системы.
Всем. Только про алгоритмы лучше Гровера для расчета того же фолдинга я лично не знаю. А почему Гровер бесполезен я уже написал.
// Квантовому компьютеру достаточна одна симуляция на «20 копиях» молекулы/системы.
Ноуп.
Всем. Только про алгоритмы лучше Гровера для расчета того же фолдинга я лично не знаю. А почему Гровер бесполезен я уже написал.
Как можно было понять из примеров, я больше об электронной структуре чем о самой динамике. Не хочу приуменьшать сложность проблемы свёртывания белков, но прежде чем дойти до этой задачи необходимо решить 20 других более сложных и фундаментальных.
Ноуп.
Угумсь.
Допустимы варианты с атаками на инфраструктуру, но тут я бы не доверял своим словам. Надо спеца безопасника-криптовалютчика-квантовика искать. Если найдете — скиньте контакты в личку, пожалуйста.
КК это узкоспециализированная история, весьма эффективная в задаче факторизации больших чисел. КК — не ASIC. Процесс майнинга биткоина — это процедура одностороннего хеширования. В данной задаче изобретение КК не дает никакого прироста.
Риском для криптовалют является поиск приватного ключа по публичному ключу — именно в этом месте используется принцип сложности разложения числа на множители. Однако публичный ключ адреса раскрывается при перемещении средств с кошелька, и очень небольшой процент пользователей использует старый адрес как адрес возврата. Также в протокол биткоина заложен механизм изменения алгоритма на устойчивый к КК. Все под контролем.
Реализация одного запутывания 2 логических кубитов требует 100.000 физических кубитов.всегда было главным аргументом. Ну пусть сейчас мы не очень хорошо умеем в коррекцию ошибок, но все равно совершенно ясно, что нужно гораздо больше физических кубитов, чтобы реализовать логические. И для 51 логического кубита, которые покажут квантовое превосходство, нам нужно тысячи и тысячи физических, всех запутанных друг с другом. Это явно не дело нескольких лет прогресса.
Поэтому для меня единственным более или менее адекватным дизайном является фотонный квантовый компьютер: мы уже умеем запутывать тысячи кубитов, они не декогерируют почти, не требуют охлаждения, просто реализовать гейты и т.д. Только размеры стола пока великоваты. Но как только они уйдут на чипы (и их научатся делать без потерь) — это будет серьезная заявка на реальный КК. Вот есть хорошая статья про это дело.
просто реализовать гейтынасколько я помню, с фотонами некоторые «гейты», необходимые для универсальности, «просто» можно реализовать только вероятностным (non-deterministic) образом, то есть потери идут после каждого и получается экспоненциальное затухание пропорционально количеству таких «гейтов».
Все же 20 dB, да на чипе, да еще через entanglement machine gun'ы — это здорово, но оочень маловероятно в ближайшие лет 20.
Чип, конечно, другая песня совсем.
Therefore, a cubic phase gate can be deterministically implemented in our architecture when necessary ancillae are injected into the circuit. This non-Gaussian cubic phase gate, together with already available multimode Gaussian gates, constitute the universal gate set for CV quantum computation.
И тут:
As a result, all gates necessary for universal CV quantum computation can be deterministically performed in this architecture.
количества одновременного спутанных кубитов
Если у вас есть запутанность в системе — она квантовая. Это, конечно, нужно верифицировать независимо.
А так даже принципиальная возможность добиться квантового превосходства не очевида, некоторые говорят, что не получится, хотя я больше доверяю доводам оптимистов.
невозможно проверить :(
проблема примерно такого же рода.
как отличить действительно квантовый компьютер, от эмуляции квантовых вычислений?
Quantum Computers have been proved to be more powerful than classical. Wrong.
This has been repeated many times and is often claimed in the literature. But there is no mathematical proof that a quantum computer that runs in polynomial quantum time cannot be simulated in polynomial classic time. None. Let me repeat that. There is no such proof. [...]
I am certainly willing [...] to take for granted that that BQP is larger than BPP.
Проблема в том, что это формальные модели, по физике сложно всё это соотносить с реальными системами.
Мои познания в классах сложности ограничены блогом Скотта Ааронсона:) У него есть пара недавних постов (1, 2, 3 — как раз про статью выше) на эту тему.
Практическая применимость ограничена, потому что нужно много кубитов и часть из них придётся использовать, чтоб поддерживать стабильность предыдущих кубитов; как отлаживать — непонятно, как быстро связывать кубиты — тоже не всегда понятно.
TL;DR: Цены не афишируются, доступность рядовому гражданину околонулевая, время амортизации на практике не посчитано, инструменты программирования только зарождаются, ещё и их маловато для задач, которые мечтают решать на квантовых компьютерах.
Добавлю про ошибки: ошибки двухкубитных операций — главное препятствие к выполнению сложных и длинных алгоритмов на существующих квантовых компьютерах, а кроме них есть ещё ошибки считывания финального состояния, которые тоже очень велики.
Есть работа, где рассматриваются различные архитектуры:
Full-Stack, Real-System Quantum Computer Studies: Architectural Comparisons and Design Insights
Можно ли собрать какой-нибудь суперкомпьютер или кластер суперкомпьютеров на кубитах (если 49 кубитов это действительно предел), запитать их от ядерного реактора (28 мегаватт на 1 машину это всё таки много), и запрограммировать их на решение какой-нибудь из задач тысячелетия или аналогичной проблемы, нерешаемой в разумный срок на обычных ПК?
Вопрос нубский конечно, но просто хочется знать.
И ещё есть ли какой-то аналог перевода кубитов в петафлопсы? Хотя бы приблизительно.
Можно ли собрать какой-нибудь суперкомпьютер или кластер суперкомпьютеров— можно. Сотни их строят.
на кубитах— так вам симуляция на суперкомпьютере, или реальный КК нужен? Реальные КК сейчас только IBM делает в состояние «бери и используй», но пока что не продаёт их, а только даёт доступ из облака.
запрограммировать их на решение какой-нибудь из задач тысячелетия— вот прямо сейчас, в 2019 году, мы столкнулись с тем, что потенциал «железа» КК которые могут создать лидеры не раскрывается в связи с тем, что у нас слишком мало теоретической, алгоритмической базы и узкое понимание в каких задачах экономически эффективно применять КК. Мы не знаем точно — для решения какой из задач они окажутся эффективны, а потому не можем направить усилия на разработку соответствующих алгоритмов и софта.
есть ли какой-то аналог перевода кубитов в петафлопсы— краткий ответ — нет. Кубит — он к условным петафлопсам относится так же «прямо», как количество ядер ЦП к ФПС в игре. Интуитивно — чем больше, тем лучше. По факту — зависит от оптимизации программы (а многопоточность и параллелизм реализованы?) и периферии.
28 мегаватт — это классический суперкомпьютер на котором проэмулировали схему из 45-49 кубитов с глубиной схемы в вентилях в 25-40 штук (сотни вентилей) — https://arxiv.org/pdf/1804.04797.pdf
Из реальных кубитов состоят не суперкомпьютеры, а квантовые компьютеры. В кластер квантовые компьютеры не объединяются. Сейчас они перегреваются и теряют когерентность за сотни микросекунд, за это время можно провести сотни операций — т.е. полезные алгоритмы не влезают.
В теории кубитовые схемы с своими "транзисторами" (вентилями CNOT, CCNOT) позволяют реализовать любую схему, доступную на классических битах и транзисторах, т.е. возможно на кубитах и кв.вентилях собрать схему АЛУ (сумматор).
Однако смысла делать классические схемы на кубитах мало, т.к. на практике их надежность на десять десятичных порядков хуже чем у битов и транзисторов (95-99% корректности у квантового вентиля против 10^-13 или лучше вероятности ошибки у транзистора), схемы слишком малы и медленны.
Поэтому на квантовых схемах пытаются делать алгоритмы с квантовыми состояниями, которые бы показали т.н. квантовое превосходство. К сожалению сейчас придуманы лишь десятки алгоритмов, которые теоретически решают задачу на квантовом компьютере быстрее чем классические алгоритмы — в том числе факторизация числа по алг.шора, бозонный сэмплер, и другие обитатели квантового зоопарка. Практически для них не хватает кубитов, надежности и количества вентилей.
Задачи тысячелетия идеальный квантовый компьютер быстрее решать не сможет, классы сложности P и NP не приравняет (P != NP; P < BQP; BQP? NP; Quantum computers… do not promise P solutions to every NP problem.… quantum computers might solve some P problems in a shorter time; https://www.quantum-bits.org/?p=1988).
Реальные квантовые компьютеры исключительно штучные, стоят по несколько (десятки-сотни) млн долларов (каждый холодильник набит сверхпроводниками, золотом и гелием-3 и стоит ~1 млн долларов).
Перевод кубитов в единицы памяти и производительности возможен в случае, когда надо точно эмулировать кв.комп на классическом — https://quantumcomputing.stackexchange.com/questions/5005/why-it-is-hard-to-simulate-a-quantum-device-by-a-classical-devices
- Для хранения эмулируемых состояний 10 кубитов нужны 8 КБ
- Для хранения состояний 20 кубитов нужны 8 МБ
- Для хранения состояний 30 кубитов нужны 8 ГБ
- Для хранения состояний 40 кубитов нужны 8 Терабайт
- Для хранения состояний 50 кубитов нужны 8 Петабайт и т.д.
По операциям — для точной эмуляции схемы на 49 кубитов из каких-то 39 "тактов" (независимых слоев вентилей) https://arxiv.org/pdf/1804.04797.pdf потребовалось 2^63 комплексных умножений — 4 Пфлопс суперкомпьютера на протяжении 4 часов. Т.е. квантовые схемы большего размера не смогут быть проэмулированы на классическом железе — 70 кубитов негде записать, реальные кв.алгоритмы многократно длиннее. Пример: алг.шора для L=2048 битного числа потребует (Table 1. Number of qubits required and circuit depth) 4 тыс.кубитов и 32 × L^3 или 3000 × L^2 т.е. 12 млрд кубитовых операций.
Доп.материалы https://www.theregister.co.uk/2018/12/06/quantum_computing_slow/
https://www.nap.edu/catalog/25196/quantum-computing-progress-and-prospects
2018 pdf — http://cs.brown.edu/courses/csci1800/sources/2018_NAE_QuantumComputing_ProgressAndProspects.pdf
The report points out that quantum computing has been on Gartner's hype list 11 times between 2000 and 2017, each time listed in the earliest stage of the hype cycle and each time said to be more than a decade away.
Given the information available to the committee, it's still too early to be able to predict the time horizon for a scalable quantum computer.
… The federal government needs to open its wallet, for who knows how long
Неплохие на вид списки:
- число кубитов https://quantumcomputingreport.com/scorecards/qubit-count/
- качество кубитов https://quantumcomputingreport.com/scorecards/qubit-quality/
- организации и технологии https://quantumcomputingreport.com/scorecards/qubit-technology/
- подборка ссылок https://quantumcomputingreport.com/our-take/
(найдено в https://quantumcomputing.stackexchange.com/questions/4100/state-of-the-art-gate-speeds-and-decoherence-times)
Если вы владеете темой, или кто-то из ваших знакомых обладает нужными знаниями, отзовитесь здесь в ЛС или на почту david@piter.com
Характеристики квантовых компьютеров