Приближенный алгоритм вычисления сложности обратимой функции в базисе Тоффоли

Рассматриваются сложность и глубина обратимых схем, состоящих из функциональных элементов NOT, CNOT и 2-CNOT при ограничениях на количество используемых дополнительных входов. Изучаются функции Шеннонa сложности $L(n, q)$ и глубины $D(n,q)$ обратимой схемы, реализующей отображение $f\colon \mathbb Z_2^n \to \mathbb Z_2^n$ , при условии, что число дополнительных входов $q$ находится в диапазоне $8n < q \lesssim n2^{n-\lceil n \mathop / \phi(n)\rceil}$ , где $\phi(n) \to \infty$ и $n \mathop / \phi(n) - \log_2 n \to \infty$ при $n \to \infty$ . Доказываются верхние оценки $L(n,q) \lesssim 2^n + 8n2^n \mathop / (\log_2 (q-4n) - \log_2 n - 2)$ и $D(n,q) \lesssim 2^{n+1}(2,5 + \log_2 n - \log_2 (\log_2 (q - 4n) - \log_2 n - 2))$ для указанного диапазона значений $q$ . Устанавливается порядок роста $L(n,q) \asymp n2^n \mathop / \log_2 q$ для таких значений $q$ , что $n^2 \lesssim q \lesssim n2^{n-\lceil n \mathop / \phi(n)\rceil}$ , где $\phi(n) \to \infty$ и $n \mathop / \phi(n) - \log_2 n \to \infty$ при $n \to \infty$ .Рассматриваются сложность и глубина обратимых схем, состоящих из функциональных элементов NOT, CNOT и 2-CNOT при ограничениях на количество используемых дополнительных входов. Изучаются функции Шеннонa сложности $L(n, q)$ и глубины $D(n,q)$ обратимой схемы, реализующей отображение $f\colon \mathbb Z_2^n \to \mathbb Z_2^n$, при условии, что число дополнительных входов $q$ находится в диапазоне $8n < q \lesssim n2^{n-\lceil n \mathop / \phi(n)\rceil}$, где $\phi(n) \to \infty$ и $n \mathop / \phi(n) - \log_2 n \to \infty$ при $n \to \infty$. Доказываются верхние оценки $L(n,q) \lesssim 2^n + 8n2^n \mathop / (\log_2 (q-4n) - \log_2 n - 2)$ и $D(n,q) \lesssim 2^{n+1}(2,5 + \log_2 n - \log_2 (\log_2 (q - 4n) - \log_2 n - 2))$ для указанного диапазона значений $q$. Устанавливается порядок роста $L(n,q) \asymp n2^n \mathop / \log_2 q$ для таких значений $q$, что $n^2 \lesssim q \lesssim n2^{n-\lceil n \mathop / \phi(n)\rceil}$, где $\phi(n) \to \infty$ и $n \mathop / \phi(n) - \log_2 n \to \infty$ при $n \to \infty$.

Дискретная математикаJan 1, 20201 citation

Преобразование квантовых флуктуаций в нелинейных системах с насыщением

Aleksandr V. Belinskii

Quantum ElectronicsJan 1, 19910 citations

Моделирование квантового алгоритма Саймона на классическом компьютере

М. А. Шемякина

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

Международный журнал гуманитарных и естественных наукJan 1, 20190 citations

Using the Information Bottleneck Method to Reduce the Complexity of LDPC Decoders

I. A Melnikov, A. Yu. Uglovskii, Alexey Kreshchuk +2 more

Одним из способов снижения сложности алгоритмов распространения доверия для декодирования кодов с малой плотностью проверок на четность является хранение предварительно вычисленной суммы сообщений в узлах переменных. В свою очередь, объем обрабатываемой информации может быть значительно снижен с помощью метода информационного сжатия (МИС), снижающего разрядность всех обновляемых сообщений. Предлагается алгоритм построения бинарной функции на основе МИС, соответствующей вычитанию. Использование разработанной функции позволяет уменьшить количество хранимых и используемых таблиц поиска для узлов переменных.Одним из способов снижения сложности алгоритмов распространения доверия для декодирования кодов с малой плотностью проверок на четность является хранение предварительно вычисленной суммы сообщений в узлах переменных. В свою очередь, объем обрабатываемой информации может быть значительно снижен с помощью метода информационного сжатия (МИС), снижающего разрядность всех обновляемых сообщений. Предлагается алгоритм построения бинарной функции на основе МИС, соответствующей вычитанию. Использование разработанной функции позволяет уменьшить количество хранимых и используемых таблиц поиска для узлов переменных.

Проблемы передачи информацииDec 15, 20241 citation

L(n, q)

и глубины

D(n,q)

обратимой схемы, реализующей отображение

f\colon \mathbb Z_2^n \to \mathbb Z_2^n

, при условии, что число дополнительных входов

q

находится в диапазоне

8n < q \lesssim n2^{n-\lceil n \mathop / \phi(n)\rceil}

, где

\phi(n) \to \infty

n \mathop / \phi(n) - \log_2 n \to \infty

при

n \to \infty

. Доказываются верхние оценки

L(n,q) \lesssim 2^n + 8n2^n \mathop / (\log_2 (q-4n) - \log_2 n - 2)

D(n,q) \lesssim 2^{n+1}(2,5 + \log_2 n - \log_2 (\log_2 (q - 4n) - \log_2 n - 2))

для указанного диапазона значений

q

. Устанавливается порядок роста

L(n,q) \asymp n2^n \mathop / \log_2 q

для таких значений

q

, что

n^2 \lesssim q \lesssim n2^{n-\lceil n \mathop / \phi(n)\rceil}

, где

\phi(n) \to \infty

n \mathop / \phi(n) - \log_2 n \to \infty

при

n \to \infty