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

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

0 голосов
/ 05 июля 2018

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

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

1 Ответ

0 голосов
/ 08 августа 2018

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

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

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

...