Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Модель квантовых вычислений
Model of quantum computing
В квантовой теории информации квантовая схема является моделью квантовых вычислений, аналогичной классическим схемам, в которой вычисление представляет собой последовательность квантовых ворот, измерений, инициализаций кубитов в известные состояния и, возможно, других операций. Минимальный набор операций, который схема должна быть способна выполнять над кубитами для обеспечения квантовых вычислений, известен как критерии Ди Винченцо. Схемы изображаются таким образом, что горизонтальная ось представляет время, начиная слева и заканчивая справа. Горизонтальные линии обозначают кубиты, а утолщенные линии – классические биты. Элементы, соединенные этими линиями, представляют собой операции, выполняемые над кубитами, такие как измерения или квантовые ворота. Эти линии определяют последовательность событий и обычно не являются физическими соединениями. Графическое представление элементов квантовой схемы описывается с использованием варианта графической нотации Пенроуза. Ричард Фейнман использовал раннюю версию обозначения квантовых схем в 1986 году.
In quantum information theory, a quantum circuit is a model for quantum computation, similar to classical circuits, in which a computation is a sequence of quantum gates, measurements, initializations of qubits to known values, and possibly other actions. The minimum set of actions that a circuit needs to be able to perform on the qubits to enable quantum computation is known as DiVincenzo's criteria. Circuits are written such that the horizontal axis is time, starting at the left hand side and ending at the right. Horizontal lines are qubits, doubled lines represent classical bits. The items that are connected by these lines are operations performed on the qubits, such as measurements or gates. These lines define the sequence of events, and are usually not physical cables. The graphical depiction of quantum circuit elements is described using a variant of the Penrose graphical notation. Richard Feynman used an early version of the quantum circuit notation in 1986.
Обратные классические логические ворота
Большинство элементарных логических элементов классического компьютера необратимы. Таким образом, например, для элемента И нельзя всегда восстановить два входных бита по выходному; например, если выходной бит равен 0, мы не можем определить, были ли входные биты 01, 10 или 00. Однако обратимые элементы в классических компьютерах легко конструируются для битовых строк любой длины; более того, они представляют практический интерес, поскольку необратимые элементы всегда увеличивают физическую энтропию. Обратимый элемент – это обратимая функция, действующая на n-битные данные и возвращающая n-битные данные, где n-битные данные – это строка битов x1, x2, …, xn длиной n. Множество n-битных данных – это пространство {0,1}n, состоящее из 2n строк, состоящих из 0 и 1. Более точно: n-битный обратимый элемент – это биективное отображение f из множества {0,1}n n-битных данных в себя. Примером такого обратимого элемента f является отображение, применяющее фиксированную перестановку к своим входам. По причинам практической инженерии обычно изучаются элементы только для небольших значений n, например, n=1, n=2 или n=3. Эти элементы можно легко описать таблицами.
Most elementary logic gates of a classical computer are not reversible. Thus, for instance, for an AND gate one cannot always recover the two input bits from the output bit; for example, if the output bit is 0, we cannot tell from this whether the input bits are 01 or 10 or 00. However, reversible gates in classical computers are easily constructed for bit strings of any length; moreover, these are actually of practical interest, since irreversible gates must always increase physical entropy. A reversible gate is a reversible function on n bit data that returns n bit data, where an n bit data is a string of bits x1,x2, ,xn of length n. The set of n bit data is the space {0,1}n, which consists of 2n strings of 0's and 1's. More precisely: an n bit reversible gate is a bijective mapping f from the set {0,1}n of n bit data onto itself. An example of such a reversible gate f is a mapping that applies a fixed permutation to its inputs. For reasons of practical engineering, one typically studies gates only for small values of n, e. g. n=1, n=2 or n=3. These gates can be easily described by tables.
Ускорение квантовых вычислительных симуляций с помощью FPGA
С появлением квантовых вычислений наблюдается значительный рост как числа разработчиков, так и доступных инструментов. Однако медленный темп технологического прогресса и высокие затраты на обслуживание, связанные с квантовыми компьютерами, ограничили широкое участие в этой области. В ответ разработчики обратились к симуляторам, таким как Qiskit от IBM, для моделирования квантового поведения без использования исключительно реального квантового оборудования. Тем не менее, симуляторы, будучи классическими компьютерами, ограничены скоростью вычислений. Фундаментальное преимущество квантовых компьютеров заключается в их способности обрабатывать кубиты, используя такие свойства, как запутанность и суперпозиция, одновременно. Запуская квантовые симуляции на классических компьютерах, теряется присущий квантовым вычислениям параллелизм. Более того, по мере увеличения числа симулируемых кубитов скорость моделирования пропорционально снижается. В квантовой схеме векторы используются для представления состояния кубитов, а различные матрицы – для представления гейтов, применяемых к кубитам. Поскольку линейная алгебра является ключевым компонентом квантовой симуляции, полевые программируемые вентильные матрицы (FPGA) могут быть использованы для ускорения симуляции квантовых вычислений. FPGA – это тип аппаратного обеспечения, которое отлично справляется с параллельным выполнением операций, поддерживает конвейеризацию, обладает встроенными ресурсами памяти с низкой задержкой доступа и обеспечивает гибкость для переконфигурации аппаратной архитектуры на лету, что делает его подходящим инструментом для обработки матричных умножений. Основная идея ускорения квантовых вычислительных симуляций заключается в переносе части вычислительной нагрузки на специализированное оборудование, такое как FPGA, для повышения скорости всего процесса моделирования. И чем больше квантовых схем (больше кубитов и гейтов) мы моделируем, тем больше выигрыша в скорости мы получаем от переноса вычислений на FPGA по сравнению с программными симуляциями на CPU. Ниже описан поток данных симуляции. Сначала пользователь вводит всю информацию о квантовой схеме, включая начальное состояние и различные гейты, через пользовательский интерфейс. Затем вся эта информация сжимается и отправляется на FPGA через аппаратные протоколы связи, такие как AXI. Далее вся информация сохраняется во встроенной памяти FPGA. И симуляция начинается, когда данные считываются из памяти и отправляются в модуль матричного умножения. После завершения всех вычислений результат отправляется обратно в память и в CPU. Предположим, мы моделируем 5-кубитные схемы, тогда нам необходимо сохранить вектор, содержащий 32 (2⁵) 16-битных значения, каждое из которых представляет квадратный корень вероятности возможного существующего состояния. Нам также необходимо сохранить матрицу 32x32, представляющую гейт. Для параллелизации этих вычислений мы можем хранить 32 строки матрицы отдельно и создать 32 аппаратных блока умножения строк, чтобы каждая строка могла вычислять умножение параллельно. Это значительно ускорит моделирование, но потребует больше аппаратных ресурсов и памяти в FPGA. Было обнаружено, что при грамотном проектировании аппаратного обеспечения можно достичь аппаратной архитектуры со временной сложностью O(n), где 'n' обозначает количество кубитов. В отличие от этого, время работы Numpy приближается к O(2^(2^n)). Этот вывод подчеркивает возможность использования FPGA для ускорения квантовых вычислительных симуляций.
With the advent of quantum computing, there has been a significant surge in both the number of developers and available tools. However, the slow pace of technological advancement and the high maintenance costs associated with quantum computers have limited broader participation in this field. In response, developers have turned to simulators, such as IBM's Qiskit, to model quantum behavior without relying solely on real quantum hardware. Nevertheless, simulators, being classical computers, are constrained by computation speed. The fundamental advantage of quantum computers lies in their ability to process qubits, leveraging properties like entanglement and superposition simultaneously. By running quantum simulations on classical computers, the inherent parallelism of quantum computing is taken away. Moreover, as the number of simulated qubits increases, the simulation's speed decreases proportionally. In a quantum circuit, the vectors are used to represent the state of the qubits and different matrices are used to represent the gate that is applied on the qubits. Since linear algebra is a major component of the quantum simulation, Field Programmable Gate Arrays (FPGAs) could be used to accelerate the simulation of quantum computing. FPGA is a kind of hardware that excels at executing operations in parallel, supports pipelining, has on chip memory resources with low access latency, and offers the flexibility to reconfigure the hardware architecture on the fly which make it a well suited tool to handle matrix multiplication. The main idea of accelerating quantum computing simulations is to offload some of the heavy computation to special hardware like FPGA in order to speed up the whole simulation process. And the bigger quantum circuits (more qubits and more gates) we simulate, the more speedup we gain from offloading to FPGA compared with software simulations on CPU. The data flow of the simulation is explained below. First, the user inputs all the information of the quantum circuit including initial state and various gates through the user interface. Then, all this information is compressed and sent to the FPGA through some hardware communication protocols like AXI. Then, all the information is stored in the on chip memory in the FPGA. And the simulation starts when the data is read from the memory and sent to the Matrix multiplication module. After all the calculation is done, the result will be sent back to the memory and to the CPU. Suppose we are simulating 5 qubit circuits, then we need to store the vector that holds 32 (2⁵) 16 bit values, each of which represents the square root probability of a possible existing state. We also need to store the 32x32 matrix that represents the gate. In order to parallel this computation, we can store the 32 rows of the matrix separately and replicate 32 row vec mult hardware such that each row can calculate the multiplication in parallel. This will dramtically speed up the simulation with a price of more hardware and memory usage in FPGA. It has been discovered that with careful hardware design, it's possible to achieve a hardware architecture with O(n) time complexity, where 'n' denotes the number of qubits. In contrast, the runtime of Numpy approaches O(2^2^n). This finding underscores the feasibility of leveraging FPGAs to accelerate quantum computing simulations.