Does Qiskit Statevector has actual speed up for Grover Search?

Question

From Qiskit document, the Statevector can be used to specify the oracle of Grover Search. After seeing the source code of the operators, it seems a statevector is converted to a rank-1 projector operator. In this case, the operator may not be unitary.

The code below can be run on a real IBMQ machine.

from qiskit import *
from qiskit.quantum_info import Statevector
from qiskit.aqua.algorithms import Grover
from qiskit import QuantumCircuit

oracle = Statevector([0,0,0,0,0,1,1,0])
good_state = ['110','101']
grover = Grover(oracle=oracle, good_state=good_state)
# backend = provider.get_backend('ibmq_lima')
backend = BasicAer.get_backend('qasm_simulator')
result = grover.run(quantum_instance=backend)
print('Result type:', type(result))
print()
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result)

However, it does not make sense to me because the operator here is not unitary.

I am wondering if Statevector of Qiskit has actual speed up or it is just for illustration of Grover Search. Besides, how does it realize when the operator is not unitary?

Answer 1

The reason for this is that the actual oracle used in the algorithm is not obtained from oracle.to_operator(). If you look up the code for Grover's algorithm, you can see the following:

grover_operator = GroverOperator(oracle=oracle,
                                 state_preparation=state_preparation,
                                 reflection_qubits=reflection_qubits,
                                 mcx_mode=mct_mode)

Then, you can take a look at the GroverOperator source code to find the following:

if isinstance(oracle, Statevector):
    from qiskit.circuit.library import Diagonal  # pylint: disable=cyclic-import
    oracle = Diagonal((-1) ** oracle.data)

What this does is explained in the documentation: it builds a diagonal matrix whose entries on the diagonal are all equal to $(-1)^{x_i}$, where the $x_i$ are the entries of your Statevector. In your case, those entries on the diagonal will all be equal to $1$ except for the ones corresponding to the states $|101\rangle$ and $|110\rangle$ which will be equal to $-1$. You can easily see that:

1. This operator is unitary
2. This operator flips the good states as it is supposed to

Since it is used for initialiazing the Grover's algorithm, I don't think it has any kind of speedup when compared to more "traditional" initialisation methods.