<p>You can also get a solution which uses only one ancillary qubit (but relies on NOT gates with multiple controls), by getting your input to algebraic normal form (e.g. with Mathematicas <code>BooleanConvert</code>).</p>
<p>For example let us use the 2x2 &quot;Sudoku&quot; example in the <a href="https://qiskit.org/textbook/ch-algorithms/grover.html#5.-Solving-Sudoku-using-Grover%27s-Algorithm-" rel="nofollow noreferrer">Qiskit book</a> (i.e. a 2x2 grid of 1bit numbers where in each column and row there should be no duplicates). Numbering the entries like</p>
<p><span class="math-container">$$
\begin{matrix}
x_0 &amp; x_1 \\
x_2 &amp; x_3
\end{matrix}
$$</span></p>
<p>our function is</p>
<p><span class="math-container">$$
f(x_0, x_1, x_2, x_3) = (x_0\oplus x_1)\land(x_2\oplus x_3)\land(x_0\oplus x_2)\land(x_1\oplus x_3)
$$</span></p>
<p>Either by hand or with computer help, we arrive at</p>
<p><span class="math-container">$$
f(x_0, x_1, x_2, x_3) =
(x_0\land x_3)\oplus
(x_1\land x_2)\oplus
(x_0\land x_1\land x_2)\oplus
(x_0\land x_1\land x_3)\oplus
(x_0\land x_2\land x_3)\oplus
(x_1\land x_2\land x_3)
$$</span></p>
<p>As you are looking for an operation that gives you <span class="math-container">$|x,y\rangle\to|x,f(x)\oplus y\rangle$</span>, we can just apply the terms one after the other. And as each term is just an AND between multiple variables, this can be written as a controlled not gate, where the not operates on <span class="math-container">$y$</span> and has a control for each appearing <span class="math-container">$x_i$</span>. For our example, this looks as follows (<code>q</code> is <span class="math-container">$x$</span> and <code>o</code> is <span class="math-container">$y$</span>)</p>
<p><a href="https://i.sstatic.net/seYAj.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/seYAj.png" alt="oracle" /></a></p>
<p>Implementing one Grover iteration, we see that it yields the two solutions</p>
<p><span class="math-container">$$
\begin{matrix}
0 &amp; 1 \\
1 &amp; 0
\end{matrix}\quad\text{and}\quad
\begin{matrix}
1 &amp; 0 \\
0 &amp; 1
\end{matrix}
$$</span></p>
<p>as expected.</p>
<p><a href="https://i.sstatic.net/wSNwt.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/wSNwt.png" alt="circuit" /></a></p>
<p><a href="https://i.sstatic.net/3eEyy.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/3eEyy.png" alt="hist" /></a></p>

CC BY-SA 4.0
2022-05-17T16:32:24.290Z
2022-05-18T09:35:54.960Z
2022-05-18T09:35:54.960Z
Daniel Hauck
<p>For many famous NP-complete problems, the Grover oracle can be constructed with quantum annealing:
<a href="https://arxiv.org/abs/2304.10488" rel="nofollow noreferrer">https://arxiv.org/abs/2304.10488</a> .
The time to realize this oracle scales only polynomially with the memory size, and no change to the leading order scaling for the Grover algorithm.</p>

CC BY-SA 4.0
2023-05-23T21:20:40.617Z
2023-05-23T21:20:40.617Z
Nik
<p>The oracle is basically just an implementation of the predicate you want to search for a satisfying solution to.</p>

<p>For example, suppose you have a 3-sat problem:</p>

<pre><code>(¬x1 ∨ ¬x3 ∨ ¬x4) ∧
    (x2 ∨ x3 ∨ ¬x4) ∧
    (x1 ∨ ¬x2 ∨ x4) ∧
    (x1 ∨ x3 ∨ x4) ∧
    (¬x1 ∨ x2 ∨ ¬x3)
</code></pre>

<p>Or, in table form with each row being a 3-clause, x meaning "this variable false", o meaning "this variable true", and space meaning "not in clause":</p>

<pre><code>1 2 3 4
-------
x   x x
  o o x
o x   o
x o x
</code></pre>

<p>Now make a circuit that computes whether the input is a solution, like this:</p>

<p><a href="https://i.sstatic.net/Saavn.png" rel="noreferrer"><img src="https://i.sstatic.net/Saavn.png" alt="solution checker"></a></p>

<p>Now, to turn your circuit into an oracle, hit the output bit with a Z gate and uncompute any garbage you made (i.e. run the compute circuit in reverse order):</p>

<p><a href="https://i.sstatic.net/x4KkE.png" rel="noreferrer"><img src="https://i.sstatic.net/x4KkE.png" alt="oracle circuit"></a></p>

<p>That's all there is to it. Compute the predicate, hit the result with a Z, uncompute the predicate. That's an oracle.</p>

<p>Iterate diffusion steps with oracle steps, and <a href="http://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%22X%22%2C%22X%22%2C%22X%22%2C%22X%22%5D%2C%5B%22H%22%2C%22H%22%2C%22H%22%2C%22H%22%5D%2C%5B%22%E2%80%A2%22%2C1%2C%22%E2%80%A2%22%2C%22%E2%80%A2%22%2C%22X%22%5D%2C%5B1%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C%22X%22%5D%2C%5B%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C%22%E2%97%A6%22%2C1%2C1%2C%22X%22%5D%2C%5B%22%E2%80%A2%22%2C%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C1%2C1%2C1%2C%22X%22%5D%2C%5B1%2C1%2C1%2C1%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22X%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Z%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Chance%22%5D%2C%5B1%2C1%2C1%2C1%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22X%22%5D%2C%5B%22%E2%80%A2%22%2C%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C1%2C1%2C1%2C%22X%22%5D%2C%5B%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C%22%E2%97%A6%22%2C1%2C1%2C%22X%22%5D%2C%5B1%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C%22X%22%5D%2C%5B%22%E2%80%A2%22%2C1%2C%22%E2%80%A2%22%2C%22%E2%80%A2%22%2C%22X%22%5D%2C%5B%22%E2%8A%96%22%2C%22%E2%8A%96%22%2C%22%E2%8A%96%22%2C%22X%22%5D%2C%5B%22%E2%80%A2%22%2C1%2C%22%E2%80%A2%22%2C%22%E2%80%A2%22%2C%22X%22%5D%2C%5B1%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C%22X%22%5D%2C%5B%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C%22%E2%97%A6%22%2C1%2C1%2C%22X%22%5D%2C%5B%22%E2%80%A2%22%2C%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C1%2C1%2C1%2C%22X%22%5D%2C%5B1%2C1%2C1%2C1%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22X%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Z%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Chance%22%5D%2C%5B1%2C1%2C1%2C1%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22X%22%5D%2C%5B%22%E2%80%A2%22%2C%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C1%2C1%2C1%2C%22X%22%5D%2C%5B%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C%22%E2%97%A6%22%2C1%2C1%2C%22X%22%5D%2C%5B1%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C%22X%22%5D%2C%5B%22%E2%80%A2%22%2C1%2C%22%E2%80%A2%22%2C%22%E2%80%A2%22%2C%22X%22%5D%2C%5B%22%E2%8A%96%22%2C%22%E2%8A%96%22%2C%22%E2%8A%96%22%2C%22X%22%5D%2C%5B%22%E2%80%A2%22%2C1%2C%22%E2%80%A2%22%2C%22%E2%80%A2%22%2C%22X%22%5D%2C%5B1%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C%22X%22%5D%2C%5B%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C%22%E2%97%A6%22%2C1%2C1%2C%22X%22%5D%2C%5B%22%E2%80%A2%22%2C%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C1%2C1%2C1%2C%22X%22%5D%2C%5B1%2C1%2C1%2C1%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22X%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Z%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Chance%22%5D%5D%7D" rel="noreferrer">you've got yourself a grover search</a>:</p>

<p><a href="http://algassert.com/quirk#circuit=%7B%22cols%22%3A%5B%5B%22X%22%2C%22X%22%2C%22X%22%2C%22X%22%5D%2C%5B%22H%22%2C%22H%22%2C%22H%22%2C%22H%22%5D%2C%5B%22%E2%80%A2%22%2C1%2C%22%E2%80%A2%22%2C%22%E2%80%A2%22%2C%22X%22%5D%2C%5B1%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C%22X%22%5D%2C%5B%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C%22%E2%97%A6%22%2C1%2C1%2C%22X%22%5D%2C%5B%22%E2%80%A2%22%2C%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C1%2C1%2C1%2C%22X%22%5D%2C%5B1%2C1%2C1%2C1%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22X%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Z%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Chance%22%5D%2C%5B1%2C1%2C1%2C1%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22X%22%5D%2C%5B%22%E2%80%A2%22%2C%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C1%2C1%2C1%2C%22X%22%5D%2C%5B%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C%22%E2%97%A6%22%2C1%2C1%2C%22X%22%5D%2C%5B1%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C%22X%22%5D%2C%5B%22%E2%80%A2%22%2C1%2C%22%E2%80%A2%22%2C%22%E2%80%A2%22%2C%22X%22%5D%2C%5B%22%E2%8A%96%22%2C%22%E2%8A%96%22%2C%22%E2%8A%96%22%2C%22X%22%5D%2C%5B%22%E2%80%A2%22%2C1%2C%22%E2%80%A2%22%2C%22%E2%80%A2%22%2C%22X%22%5D%2C%5B1%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C%22X%22%5D%2C%5B%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C%22%E2%97%A6%22%2C1%2C1%2C%22X%22%5D%2C%5B%22%E2%80%A2%22%2C%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C1%2C1%2C1%2C%22X%22%5D%2C%5B1%2C1%2C1%2C1%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22X%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Z%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Chance%22%5D%2C%5B1%2C1%2C1%2C1%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22X%22%5D%2C%5B%22%E2%80%A2%22%2C%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C1%2C1%2C1%2C%22X%22%5D%2C%5B%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C%22%E2%97%A6%22%2C1%2C1%2C%22X%22%5D%2C%5B1%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C%22X%22%5D%2C%5B%22%E2%80%A2%22%2C1%2C%22%E2%80%A2%22%2C%22%E2%80%A2%22%2C%22X%22%5D%2C%5B%22%E2%8A%96%22%2C%22%E2%8A%96%22%2C%22%E2%8A%96%22%2C%22X%22%5D%2C%5B%22%E2%80%A2%22%2C1%2C%22%E2%80%A2%22%2C%22%E2%80%A2%22%2C%22X%22%5D%2C%5B1%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C%22X%22%5D%2C%5B%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C%22%E2%97%A6%22%2C1%2C1%2C%22X%22%5D%2C%5B%22%E2%80%A2%22%2C%22%E2%97%A6%22%2C%22%E2%80%A2%22%2C1%2C1%2C1%2C1%2C%22X%22%5D%2C%5B1%2C1%2C1%2C1%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22%E2%97%A6%22%2C%22X%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Z%22%5D%2C%5B1%2C1%2C1%2C1%2C1%2C1%2C1%2C1%2C%22Chance%22%5D%5D%7D" rel="noreferrer"><img src="https://i.sstatic.net/thzME.png" alt="grover search"></a></p>

<p>... although you should probably pick an example with fewer solutions, so the progress is gradual (instead of rotating along the start-state-solution-state plane by more than 90 degrees per step as my example is).</p>

CC BY-SA 3.0
2017-07-06T18:03:06.343Z
Thanks, this was immensely helpful. Incredibly clear, answered everything I asked (and even used common quantum gates!) Is there any reason you decide to change all of your starting qubits to the |1> state before putting them in superposition with Hadamard gates instead of just putting the |0> state qubits through Hadamards (i.e. is there an advantage to this)? Also, what operation is that for your diffusion steps? Looks like controlled X, but are you using |1>'s or |0>'s as controls?
Will
CC BY-SA 3.0
2017-07-06T18:43:10.060Z
@Will I used a different starting state. You can do that as long as you also change the state negated by the diffusion operator (they have to match). All starting/diffusion states that have equal angle-distance to every computational basis state work equally well. The little circled-plus control in my diagram is an "X-axis control", which is equivalent to a normal control surrounded by Hadamard gates. It looks like a NOT because [they're interchangeable](http://algassert.com/post/1706). My starting/diffusion state is $(\frac{1}{\sqrt{2}} |0\rangle - \frac{1}{\sqrt{2}} |1\rangle)^{\otimes n}$.
Craig Gidney
CC BY-SA 3.0
2017-07-11T13:17:21.500Z
Fantastic answer, and thanks for the link to http://algassert.com/quirk !
Frédéric Grosshans
CC BY-SA 4.0
2020-09-15T15:12:16.727Z
In addition to this great answer, you can get rid of the last qubit by directly using a multi-controlled `Z` gate having as target the last but one qubit [link](https://tinyurl.com/y6ey2287)
tigerjack
CC BY-SA 4.0
2020-09-15T19:29:12.063Z
@tigerjack89 You need to conjugate that Z gate with X gates to make it act like an off control instead of an on control.
Craig Gidney
CC BY-SA 4.0
2020-09-16T07:15:44.057Z
@CraigGidney I'm not sure I follow your comment. I just replaced the multi controlled not (MCX) + Z + MCX with a simple MCZ. In both cases, the Z acts only on the $|1\rangle$ state, leaving $|0\rangle$ untouched.
tigerjack
CC BY-SA 3.0
2017-07-06T00:35:47.767Z
2017-07-06T00:35:47.767Z
Craig Gidney
<p>In Mike and Ike's "Quantum Computation and Quantum Information", Grover's algorithm is explained in great detail. However, in the book, and in all explanations I have found online for Grover's algorithm, there seems to be no mention of how Grover's Oracle is constructed, unless we already know which state it is that we are searching for, defeating the purpose of the algorithm. Specifically, my question is this: given some f(x) such that for some x value, f(x)=1, but for all others, f(x)=0, how does one construct an oracle that will get us from our initial, arbitrary state |x>|y> to |x>|y+f(x)>? As much explicit detail as possible (perhaps an example?) would be greatly appreciated. If such a construction for any arbitrary function is possible with Hadamard, Pauli, or other standard quantum gates, a method for construction with these would be appreciated.</p>

CC BY-SA 3.0
2017-07-04T16:38:30.960Z
"here seems to be no mention of how Grover's Oracle is constructed, unless we already know which state it is that we are searching for, defeating the purpose of the algorithm. " ... "Grover's Oracle" is the *problem to be solved.* You don't construct it. You're given (oracle access to) it and asked to perform computation to uncover the value. If it helps, pretend that *I* construct the oracle, and then ask *you* to solve the problem. (Also, note that reading/writing/preparing a database of $N$ items takes longer than running Grover's $\sqrt{N}$-time algorithm.)
Daniel Apon
CC BY-SA 3.0
2017-07-05T18:11:37.877Z
But what if instead of being given the oracle, we are given some f(x)? Imagine we are solving a 3-SAT problem and want to use Grover's to provide a speedup to the solution. We know the f(x) in question (the 3-SAT truth clauses), but don't necessarily know which bit string x will yield a true result when plugged into the 3-SAT. Mustn't there be a way to construct an oracle from the 3-SAT function to find the correct bit string? If there isn't, and it is as you suggest, something to be provided by someone else, Grover's algorithm seems rather artificial, merely an exercise given to you.
Will
CC BY-SA 4.0
2021-06-28T12:57:41.240Z
I'm confused and would appreaciate any help I can get from you. [![please look at my setup](https://i.sstatic.net/TTTJw.jpg)](https://i.sstatic.net/TTTJw.jpg) I have q0 and q1 passing an "H" gate then the toffoli with an !0> - switching !0> + !11> to !111> Same with the next gate When running I see the expected results. But what drives me nuts: From the explaination in the article I would understand
my setting also as a ^(q0 & q1) Then the result should show me "00" as solution for q0 and q1. What's wrong with me idea??? Thanks a lot!
-Jerry
jerry
<quantum-computing><quantum-information><oracles><search-problem><black-box>
Oracle Construction for Grover's Algorithm
Will
# Oracle Construction for Grover's Algorithm

(Asked by: username_0 on 2017-07-04)

In Mike and Ike's "Quantum Computation and Quantum Information", Grover's algorithm is explained in great detail. However, in the book, and in all explanations I have found online for Grover's algorithm, there seems to be no mention of how Grover's Oracle is constructed, unless we already know which state it is that we are searching for, defeating the purpose of the algorithm. Specifically, my question is this: given some f(x) such that for some x value, f(x)=1, but for all others, f(x)=0, how does one construct an oracle that will get us from our initial, arbitrary state |x>|y> to |x>|y+f(x)>? As much explicit detail as possible (perhaps an example?) would be greatly appreciated. If such a construction for any arbitrary function is possible with Hadamard, Pauli, or other standard quantum gates, a method for construction with these would be appreciated.

**Tags:** quantum-computing, quantum-information, oracles, search-problem, black-box

> **Comments:**
> **username_1**: "here seems to be no mention of how Grover's Oracle is constructed, unless we already know which state it is that we are searching for, defeating the purpose of the algorithm. " ... "Grover's Oracle" is the *problem to be solved.* You don't construct it. You're given (oracle access to) it and asked to perform computation to uncover the value. If it helps, pretend that *I* construct the oracle, and then ask *you* to solve the problem. (Also, note that reading/writing/preparing a database of $N$ items takes longer than running Grover's $\sqrt{N}$-time algorithm.)  
> **username_0**: But what if instead of being given the oracle, we are given some f(x)? Imagine we are solving a 3-SAT problem and want to use Grover's to provide a speedup to the solution. We know the f(x) in question (the 3-SAT truth clauses), but don't necessarily know which bit string x will yield a true result when plugged into the 3-SAT. Mustn't there be a way to construct an oracle from the 3-SAT function to find the correct bit string? If there isn't, and it is as you suggest, something to be provided by someone else, Grover's algorithm seems rather artificial, merely an exercise given to you.  
> **username_2**: I'm confused and would appreaciate any help I can get from you. [![please look at my setup](https://i.sstatic.net/TTTJw.jpg)](https://i.sstatic.net/TTTJw.jpg) I have q0 and q1 passing an "H" gate then the toffoli with an !0> - switching !0> + !11> to !111> Same with the next gate When running I see the expected results. But what drives me nuts: From the explaination in the article I would understand my setting also as a ^(q0 & q1) Then the result should show me "00" as solution for q0 and q1. What's wrong with me idea??? Thanks a lot! -Jerry  

---

## 3 answers

### Answer by username_5 on 2017-07-06. Score: 30 | Accepted answer

The oracle is basically just an implementation of the predicate you want to search for a satisfying solution to.
For example, suppose you have a 3-sat problem:
(¬x1 ∨ ¬x3 ∨ ¬x4) ∧
    (x2 ∨ x3 ∨ ¬x4) ∧
    (x1 ∨ ¬x2 ∨ x4) ∧
    (x1 ∨ x3 ∨ x4) ∧
    (¬x1 ∨ x2 ∨ ¬x3)

Or, in table form with each row being a 3-clause, x meaning "this variable false", o meaning "this variable true", and space meaning "not in clause":
1 2 3 4
-------
x   x x
  o o x
o x   o
x o x

Now make a circuit that computes whether the input is a solution, like this:

Now, to turn your circuit into an oracle, hit the output bit with a Z gate and uncompute any garbage you made (i.e. run the compute circuit in reverse order):

That's all there is to it. Compute the predicate, hit the result with a Z, uncompute the predicate. That's an oracle.
Iterate diffusion steps with oracle steps, and you've got yourself a grover search:

... although you should probably pick an example with fewer solutions, so the progress is gradual (instead of rotating along the start-state-solution-state plane by more than 90 degrees per step as my example is).

> **Comments:**
> **username_0**: Thanks, this was immensely helpful. Incredibly clear, answered everything I asked (and even used common quantum gates!) Is there any reason you decide to change all of your starting qubits to the |1> state before putting them in superposition with Hadamard gates instead of just putting the |0> state qubits through Hadamards (i.e. is there an advantage to this)? Also, what operation is that for your diffusion steps? Looks like controlled X, but are you using |1>'s or |0>'s as controls?  
> **username_5**: @username_0 I used a different starting state. You can do that as long as you also change the state negated by the diffusion operator (they have to match). All starting/diffusion states that have equal angle-distance to every computational basis state work equally well. The little circled-plus control in my diagram is an "X-axis control", which is equivalent to a normal control surrounded by Hadamard gates. It looks like a NOT because [they're interchangeable](http://algassert.com/post/1706). My starting/diffusion state is $(\frac{1}{\sqrt{2}} |0\rangle - \frac{1}{\sqrt{2}} |1\rangle)^{\otimes n}$.  
> **username_6**: Fantastic answer, and thanks for the link to http://algassert.com/quirk !  
> **username_7**: In addition to this great answer, you can get rid of the last qubit by directly using a multi-controlled `Z` gate having as target the last but one qubit [link](https://tinyurl.com/y6ey2287)  
> **username_5**: @username_789 You need to conjugate that Z gate with X gates to make it act like an off control instead of an on control.  
> **username_7**: @CraigGidney I'm not sure I follow your comment. I just replaced the multi controlled not (MCX) + Z + MCX with a simple MCZ. In both cases, the Z acts only on the $|1\rangle$ state, leaving $|0\rangle$ untouched.  

---

### Answer by username_3 on 2022-05-17. Score: 1

You can also get a solution which uses only one ancillary qubit (but relies on NOT gates with multiple controls), by getting your input to algebraic normal form (e.g. with Mathematicas `BooleanConvert`).

For example let us use the 2x2 "Sudoku" example in the [Qiskit book](https://qiskit.org/textbook/ch-algorithms/grover.html#5.-Solving-Sudoku-using-Grover%27s-Algorithm-) (i.e. a 2x2 grid of 1bit numbers where in each column and row there should be no duplicates). Numbering the entries like

$$
\begin{matrix}
x\_0 & x\_1 \\
x\_2 & x\_3
\end{matrix}
$$

our function is

$$
f(x\_0, x\_1, x\_2, x\_3) = (x\_0\oplus x\_1)\land(x\_2\oplus x\_3)\land(x\_0\oplus x\_2)\land(x\_1\oplus x\_3)
$$

Either by hand or with computer help, we arrive at

$$
f(x\_0, x\_1, x\_2, x\_3) =
(x\_0\land x\_3)\oplus
(x\_1\land x\_2)\oplus
(x\_0\land x\_1\land x\_2)\oplus
(x\_0\land x\_1\land x\_3)\oplus
(x\_0\land x\_2\land x\_3)\oplus
(x\_1\land x\_2\land x\_3)
$$

As you are looking for an operation that gives you $|x,y\rangle\to|x,f(x)\oplus y\rangle$, we can just apply the terms one after the other. And as each term is just an AND between multiple variables, this can be written as a controlled not gate, where the not operates on $y$ and has a control for each appearing $x\_i$. For our example, this looks as follows (`q` is $x$ and `o` is $y$)

[![oracle](https://i.sstatic.net/seYAj.png)](https://i.sstatic.net/seYAj.png)

Implementing one Grover iteration, we see that it yields the two solutions

$$
\begin{matrix}
0 & 1 \\
1 & 0
\end{matrix}\quad\text{and}\quad
\begin{matrix}
1 & 0 \\
0 & 1
\end{matrix}
$$

as expected.

[![circuit](https://i.sstatic.net/wSNwt.png)](https://i.sstatic.net/wSNwt.png)

[![hist](https://i.sstatic.net/3eEyy.png)](https://i.sstatic.net/3eEyy.png)


---

### Answer by username_4 on 2023-05-23. Score: -2

For many famous NP-complete problems, the Grover oracle can be constructed with quantum annealing:
<https://arxiv.org/abs/2304.10488> .
The time to realize this oracle scales only polynomially with the memory size, and no change to the leading order scaling for the Grover algorithm.


---

