Почему важно устранить мусорные кубиты?

18

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

Итак, главная схема, как фактически становится | х | 0 | f ( x ) | г , где | г обозначает кубит мусора (ов).|x|f(x)|x|0|f(x)|g
|g

Цепи, которые сохраняют исходное значение, заканчиваются на |x|0|0|x|f(x)|g

Я понимаю, что мусорные кубиты неизбежны, если мы хотим, чтобы схема оставалась обратимой, но многие источники утверждаю, что важно их устранить. Почему это так?1


Из-за запросов на источники, см., Например,эту статью arXiv, стр. 8, в которой говорится1

Однако каждая из этих простых операций содержит ряд дополнительных вспомогательных кубитов, которые служат для хранения промежуточных результатов, но не имеют отношения к концу. Поэтому, чтобы не тратить лишнее пространство [sic], важно сбросить эти кубиты на 0, чтобы мы могли их повторно использовать

или это бумага arXiv, которая говорит

Удаление мусорных кубитов и вспомогательных кубитов имеет важное значение при разработке эффективной квантовой цепи.

или много других источников - поиск Google производит много хитов.

bytebuster
источник

Ответы:

16

f:{0,1}{0,1}fе(Икс)знак равноИкс, Допустим, у нас была схемаСе какие входы Икс и выводы е(Икс), Теперь, конечно, это была обратимая схема, и ее можно было реализовать с помощью унитарного преобразования.|x|x. Now, we could feed in 12|0+12|1 and the output would also be 12|0+12|1. Let us now apply Hadamard transform gate and measure what we get. If you apply the Hadamard transform to this state 12|0+12|1, you get the |0 state, and you see 0 with probability 1. In this case there was no junk created in the intermediate steps, while converting the classical circuit to a quantum circuit.

But, let's say we created some junk in an intermediate step when using a circuit like this one:

enter image description here.

For this circuit, if we start off in the state |x|0=(12|0+12|1)|0, after the first step we get 12|00+12|11. If we apply the Hadamard transform to the first qubit, we end up with:

12|00+12|01+12|10+12|11

If we make a measurement on the first qubit we get 0 with probability 12, unlike in the previous case where we could see 0 with probability 1! The only difference between the two cases was the creation of a junk bit in an intermediate step, which was not gotten rid of, thus leading to a difference in the final result of the computation (since the junk qubit got entangled with the other qubit). We will see a different interference pattern than in the previous case when the Hadamard transform is applied. This is exactly why we don't like to keep junk around when we are doing quantum computation: it prevents interference.

Source: Professor Umesh Vazirani's lecture on EdX.

Sanchayan Dutta
источник
3

If you want to use a quantum circuit as a subroutine (such as an oracle) to a quantum algorithm that makes use of interference, you must allow interference by a process known as uncomputing your ancillary (or, in your words, garbage) qubits. Uncomputing is always possible: Since your gates are reversible, you can just apply their inverse. That is, after the step you mentioned, |x|0|0|x|f(x)|g, you perform another computation (or uncomputation) that leads to |x|f(x)|0.

pyramids
источник