Как реализовать оператор диффузии Гровера в Q#?

Question

Как видно из названия, как реализовать оператор диффузии Гровера в Q#? Я знаю, что это определяется как 2 ⟨s|s⟩ - I где |s⟩ является равномерным состоянием для любого произвольного числа кубитов. Это может быть дополнительно определено в терминах ворот Z0 (он назывался U0), расположенных между H-воротами. Я не смог найти никакой функции в квантовых примитивах и документах canon, начиная с возможных имен, таких как Grover, diff и т. Д.

Я не хочу использовать функцию AmpAmpByOracle так как это реализация очень высокого уровня и не очищает мое понимание. Я хочу реализовать функцию, которая принимает оракула Uf(неизвестно мне, предположим) и количество кубитов, которое он принимает (N), и выполняет алгоритм Гровера, просто следуя схеме, приведенной в Алгоритме Гровера | Википедии и измерить требуемое состояние, измерив все N кубитов в конце итераций r = приблизительно (2^(N/2)).

Answer 1

Операция диффузии немного сложнее. Я считаю, что проще всего разложить его на куски:

1. Как вы указали, гораздо проще взглянуть на операцию диффузии в X-базисе. Если вы применяете H к каждому кубиту до и после, то в середине единообразное состояние выглядит как состояние 000... 0.
2. Операция диффузии (в базисе X) равна -1 в состоянии 000... 0 и идентификаторе (+1) во всех других базовых состояниях. Первый шаг - выбрать состояние 000... 0; Я могу сделать это с мультиуправляемым гейтом X - за исключением того, что мне нужно сначала перевернуть все кубиты от 0 до 1 (и наоборот), поскольку контролируемые операции ищут 1 с, а не 0 с. Конечно, после контролируемого X мне нужно отменить сальто.
3. Чтобы сгенерировать -1, я могу начать с ancilla в состоянии |->, так что X превратит его в -|->.
4. После того, как я покончу со всем, мне нужно сбросить вспомогательное устройство, чтобы я мог вернуть его в состояние |0>.

Это все превращается в:

// register is the Qubit[] that we want to apply the diffusion operation to
using (ancillae = Qubit[1])
{
  let ancilla = ancillae[0];

  X(ancilla); // Puts the ancilla into the |1> state
  H(ancilla); // And now into the |-> state

  ApplyToEach(H, register);  // Put the register qubits into the X basis
  ApplyToEach(X, register);  // Flip 0->1 and 1->0
  (Controlled X)(register, ancilla);  // Do the controlled flip of the ancilla
  ApplyToEach(X, register);  // Undo the flip
  ApplyToEach(H, register);  // Undo the basis change

  H(ancilla); // Put the ancilla back into |1>
  X(ancilla); // And back to |0> so we can return it
}

Это не скомпилированный код, поэтому могут быть некоторые опечатки...