2

In this example implementation of Grovers Algorithm from the Qiskit Textbook which solves a $2\times 2$ sudoku puzzle:

https://qiskit.org/textbook/ch-algorithms/grover.html

The circuit iterates twice (see picture)

My question is:

How is the data in the $c_0 - c_3$ and out0 qubits utilised.

To me it looks like $c_0 - c_3$ and out are never fed back into the $v_0 - v_3$ qubits, and $v_0 - v_3$ are the only ones that are measured at the end.

I'm not sure if I've misinterpreted how entanglement works here, or how the CX gates work.

enter image description here

glS
  • 27,510
  • 7
  • 37
  • 125
Ben
  • 23
  • 2

1 Answers1

1

The quantum register c can be regarded as ancilla. For the first part of each iteration(before the CCCC-NOT), each two cx compares if the state of the two qubits is identical, if not, one ancilla will be converted to the state $|1\rangle$. The CCCC-NOT checks whether the four ancillae are all $|1\rangle$, if so, a phase-flip operation is implemented.

The second part of each iteration(between CCCC-NOT and the diffusion unitary) converts the ancillae into its original state($|0000\rangle$, for reversibility). The action of diffusion unitary should be familiar to you.

Introduce ancilla into the quantum circuit will certainly increase the difficulty of classical simulation, but it may decrease the difficulty of designing an algorithm (sometimes it is impossible to achieve the goal without the ancilla).

Yitian Wang
  • 1,008
  • 6
  • 16