Tag Info

2

For me, Sam Palmer's answer starts to have the right sort of structure. But, for the sake of being more explicit: We're interested in solving problems that are in the class NP, i.e. they have a function that lets you recognise correct answers. It is sufficient for me to talk about one specific case: 3-SAT. That is because this case is NP-complete - every ...

5

Grover's algorithm We are given a function $f(a)$ such that $f(a)=0$ for all of the $N$ possible values of $a$, except when $a=\omega$ in which case we have $f(\omega)=1$. Assuming that this $f(a)$ can be calculated using a classical reversible code or hardware, we can find $\omega$ with $\mathcal{O}(\sqrt{N})$ steps using a quantum circuit as opposed to a ...

1

There is a much simpler way to approach this task. It requires only two observations: You can always convert a marking oracle to a phase oracle using the phase kickback trick (discussed earlier in the tutorial). Some tasks in this tutorial prohibit using extra qubits for this purpose to push you towards a solution that doesn't rely on that, but this task ...

2

Number of states marked isn't a strict correspondence with number of CZ gates: your new oracle still marks two states, but, rather than $\left|101\right>$ and $\left|110\right>$, it marks $\left|101\right>$ and $\left|111\right>$. To see this, remember a $Z$ gate flips the sign of a $\left|1\right>$: if the $Z$ gate is applied to a 1 and the ...

4

For adiabatic Grover you want the ground state of the final Hamiltonian to be the marked item. The key idea with Grover is that the item is hard to find but easy to verify. So the idea is you embed the 'easy to verify' into the Hamiltonian, which is the similar as marking the item via the phase oracle in the gate model. For example consider a simple case ...

Top 50 recent answers are included