В обратимых вычислениях вспомогательные биты — это дополнительные биты, используемые для реализации необратимых логических операций. В классических вычислениях любой бит памяти может быть включен или выключен по желанию, не требуя никаких предварительных знаний или дополнительной сложности. Однако в квантовых вычислениях или классических обратимых вычислениях это не так. В этих моделях вычислений все операции с памятью компьютера должны быть обратимыми, и включение или выключение бита приведет к потере информации о начальном значении этого бита. По этой причине в квантовом алгоритме нет способа детерминированно поместить биты в определенное предписанное состояние, если только не предоставлен доступ к битам, исходное состояние которых известно заранее. Такие биты, значения которых известны априори , известны как вспомогательные биты в квантовой или обратимой вычислительной задаче .
Тривиальное использование вспомогательных битов — понижение уровня сложных квантовых вентилей до простых вентилей. Например, размещая элементы управления на вспомогательных битах, вентиль Тоффоли может использоваться как управляемый вентиль НЕ или вентиль НЕ . [1] : 29
Для классических обратимых вычислений известно, что постоянное число O(1) вспомогательных битов необходимо и достаточно для универсальных вычислений. [2] Дополнительные вспомогательные биты не нужны, но дополнительное рабочее пространство может позволить более простые конструкции схем , которые используют меньше вентилей. [1] : 131
Концепция вспомогательного бита может быть расширена для квантовых вычислений в терминах вспомогательных кубитов , которые могут использоваться, например, для квантовой коррекции ошибок . [3] Одним из примечательных примеров использования вспомогательных кубитов в квантовых вычислениях является алгоритм Дойча–Йожи .
Квантовый катализ использует вспомогательные кубиты для хранения запутанных состояний , что позволяет выполнять задачи, которые обычно невозможны с помощью локальных операций и классической коммуникации (LOCC). [4]