2
$\begingroup$

In a two-bit string array i.e [00,01,10,11], how to find 01 & 10 together using the Grover search algorithm. What will be the amplitude amplification circuit?

$\endgroup$

2 Answers 2

1
$\begingroup$

In the example you mentioned in the question, the Grover algorithm will not work because there are as many marked states ($|01\rangle$ and $|10\rangle$) as unmarked ones ($|00\rangle$ and $|11\rangle$), and an imbalance is required for amplitude amplification of the marked states to take place. If you wish to amplify a single basis state (e.g., $|01\rangle$), then a single iteration of the Grover algorithm will suffice to obtain it with certainty. Cf. Chapter 8 of Jonathan Jones and Dieter Jaksch's "Quantum Information, Computation and Communication" for a detailed and pedagogical account of this case.

$\endgroup$
1
$\begingroup$

bm442 is correct. With a 2-qubit system, only a single iteration of the Grover operator is applied and the state ends up like this (printed in my own infrastructure):

|000> (|0>):  ampl: -0.35+0.00j prob: 0.12 Phase: 180.0
|001> (|1>):  ampl: +0.35+0.00j prob: 0.12 Phase:   0.0
|010> (|2>):  ampl: +0.35+0.00j prob: 0.12 Phase:   0.0
|011> (|3>):  ampl: -0.35+0.00j prob: 0.12 Phase: 180.0
|100> (|4>):  ampl: -0.35+0.00j prob: 0.12 Phase: 180.0
|101> (|5>):  ampl: +0.35+0.00j prob: 0.12 Phase:   0.0
|110> (|6>):  ampl: +0.35+0.00j prob: 0.12 Phase:   0.0
|111> (|7>):  ampl: -0.35+0.00j prob: 0.12 Phase: 180.0

On measurement, each state has the same probability - whether or not you find the solution is random.

What you can do is perhaps add additional qubits and mark states like $|000 01\rangle$ and $|000 10\rangle$. If you use a matrix operator to mark those states, this appears quite straightforward.

If you wanted to make an explicit circuit, you have to construct it such that only these two states lead to an ancillary $a_2$ being set to 1. This can be achieved with 2 multi-controlled Pauli X-gates. For $|000 01\rangle$ you would have the first 4 qubits be controlled by 0, meaning you put a Pauli X-gate before and after the multi-controlled X-gate, to apply a multi-controlled X-gate on ancillary $a_0$. Similar for the other state, which will multi-control another ancilla $a_1$. Finally, an X-gate controlled by both $a_0$ and $a_1$ applies another X-gate on $a_2$.

This final ancilla $a_2$ (together with the first 5 qubits) you will then have to feed into the diffusion circuit.

Again, I have put versions with operators and circuits online, maybe this helps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.