# Grover search for basis states with complex coefficents and multiple marked states

I tried to run Grover's search for basis states with complex coefficients, including the marked basis (complex coefficients because the states are obtained from inverse QFT), but it could not amplify the marked basis effectively. I think it has to do with the inverse-about-the-mean part since now the mean is complex but I'm not sure how to analyse the behavior exactly. Can someone help to explain why is that so and is there any way to salvage the situation? And also if I want to amplify multiple marked states concurrently what is the most optimal diffusion operator?

This is the circuit I used: first I initialized the initial state (a four-qubit system) as

$$|x\rangle=\frac{1}{\sqrt{8}}(1,1,1,1,1,1,1 ,1,0,0,0,0,0,0,0,0)^T$$

then I applied this inverse QFT circuit. The resultant state vector is

$$(0.707+0i, 0.088-0.444i, 0, 0.088-0.059i, 0, 0.088-0.132i, 0, 0.088-0.018i, 0, 0.088+0.018i, 0, 0.088+0.132i, 0, 0.088+0.059i, 0, 0.088+0.444i)^T$$

Note: values are rounded

Then I negated the states of interest $$|0000\rangle$$, $$|0001\rangle$$, $$1111\rangle$$ by using this circuit (I believe you guys can tell which part of it is for which states if now please let me know:

Then I applied the diffusion operator. Notice that I negated the phase of $$|0000\rangle$$ instead of the rest. This resulted in a $$180^o$$ global phase difference. In the Grover search case where all coefficients are real the result for measurement is identical to marking all the rest states but I'm not sure for complex-valued coefficient will there be any difference.

These are the qskit codes:

import numpy as np
import math
from qiskit import *
%matplotlib inline

import math
from qiskit import QuantumRegister, ClassicalRegister, QuantumCircuit, execute, BasicAer

#initialization
q = QuantumRegister(5, "q")
c = ClassicalRegister(4, 'c')
circ = QuantumCircuit(q, c, name="initializer_circ")

desired_vector = [
1 / math.sqrt(8),
1 / math.sqrt(8),
1 / math.sqrt(8),
1 / math.sqrt(8),
1 / math.sqrt(8),
1 / math.sqrt(8),
1 / math.sqrt(8),
1 / math.sqrt(8),
0,
0,
0,
0,
0,
0,
0,
0]

circ.initialize(desired_vector, [q[0], q[1], q[2], q[3]])

#circ.draw()

#IQFT
sub_q = QuantumRegister(4)
sub_circ = QuantumCircuit(sub_q, name='IQFT')
sub_circ.swap(sub_q[0], sub_q[3])
for j in range(4):
for k in range(j):
sub_circ.cu1(math.pi/float(2**(j-k)), sub_q[j], sub_q[k])
sub_circ.h(sub_q[j])
sub_circ=sub_circ.inverse()
sub_inst = sub_circ.to_instruction()
circ.append(sub_inst, [q[0],q[1],q[2],q[3]])
#circ.draw()

#phase inverstion of |0000>
circ.x(q[0])
circ.x(q[1])
circ.x(q[2])
circ.x(q[3])
circ.h(q[3])
circ.ccx(q[0], q[1], q[4])
circ.ccx(q[2], q[4], q[3])
circ.ccx(q[0], q[1], q[4])
circ.h(q[3])
circ.x(q[0])
circ.x(q[1])
circ.x(q[2])
circ.x(q[3])

#circ.draw()

#phase inverstion of |0001>
circ.x(q[1])
circ.x(q[2])
circ.x(q[3])
circ.h(q[3])
circ.ccx(q[0], q[1], q[4])
circ.ccx(q[2], q[4], q[3])
circ.ccx(q[0], q[1], q[4])
circ.h(q[3])
circ.x(q[1])
circ.x(q[2])
circ.x(q[3])

#circ.draw()

#phase inverstion of |1111>
circ.h(q[3])
circ.ccx(q[0], q[1], q[4])
circ.ccx(q[2], q[4], q[3])
circ.ccx(q[0], q[1], q[4])
circ.h(q[3])

#circ.draw()

#Diffusion Operator
circ.h(q[0])
circ.h(q[1])
circ.h(q[2])
circ.h(q[3])
circ.x(q[0])
circ.x(q[1])
circ.x(q[2])
circ.x(q[3])
circ.h(q[3])
circ.ccx(q[0], q[1], q[4])
circ.ccx(q[2], q[4], q[3])
circ.ccx(q[0], q[1], q[4])
circ.h(q[3])
circ.x(q[0])
circ.x(q[1])
circ.x(q[2])
circ.x(q[3])
circ.h(q[0])
circ.h(q[1])
circ.h(q[2])
circ.h(q[3])
#circ.draw()

#check the state vector at any stage run the following code:

# Import Aer
from qiskit import BasicAer

# Run the quantum circuit on a statevector simulator backend
backend = BasicAer.get_backend('statevector_simulator')
# Create a Quantum Program for execution
job = execute(circ, backend)
result = job.result()
outputstate = result.get_statevector(circ, decimals=3)
print(outputstate)
print(np.absolute(outputstate))


Note: uncomment #circ.draw() to plot the circuit

• By the way will the amplitude amplification change the phases of each basis state? I hope not since the phases contain important information. – Zzy1130 Jun 12 '19 at 10:54
• Any basis should work fine, complex coefficients are not a problem. You likely have a mistake elsewhere. Can you give more details about your approach so we can help identify the issue? – bRost03 Jun 12 '19 at 12:13
• Firstly I initialized my state as [1 / sqrt(8),1 / sqrt(8),1 / sqrt(8),1 / sqrt(8),1 / sqrt(8),1 /sqrt(8),1 /sqrt(8),1 / sqrt(8),0,0,0,0,0,0,0,0] (a four-qubit system). Then I applied inverse QFT and obtained [0. 707+0.j, 0.088-0.444j, 0, 0.088-0.059j, 0, 0.088-0.132j, 0, 0.088-0.018j, 0, 0.088+0.018j, 0, 0.088+0.132j, 0, 0.088+0.059j, 0, 0.088+0.444j] (rounded values). Now if you mark state |0000> and apply diffusion operator |0000> will not get amplified. – Zzy1130 Jun 12 '19 at 12:28
• I actually wanted to minimize state |0000>, |0001> and |1111> ( I have tired in real-value coefficient case (I take absolute values of each entry and treat it as a new array) you can actually mark multiple states (negating their phases) and apply diffusion operator and iterate until they gets minimized. But when I do the same operation on the complex values it really behaves differently. – Zzy1130 Jun 12 '19 at 12:32
• The inverse QFT should only act on the first 4 registers. – bRost03 Jun 12 '19 at 12:37