6
\$\begingroup\$

This code was tested on IBM's 5-Qubit processor as an implementation of Grover's search algorithm, but for an unknown number of solutions. This code is based on Arthur Pittenger's book, "An Introduction to Quantum Computing Algorithms" and the mathematical structure was posted as a proof-verification question here.

h q[0];
h q[1];
x q[2];
s q[0];
cx q[1], q[2];
t q[3];
cx q[0], q[2];
s q[3];
x q[0];
z q[1];
s q[2];
tdg q[3];
cx q[0], q[2];
id q[3];
cx q[1], q[2];
h q[0];
h q[1];
h q[2];
x q[0];
x q[1];
x q[2];
cx q[0], q[2];
h q[0];
cx q[1], q[2];
s q[2];
h q[2];
tdg q[2];
h q[2];
measure q[0];
measure q[1];
measure q[2];
measure q[3];
measure q[4];

For successful implementations of Grover's algorithm, there has to be a bias towards $$\vert 0 \rangle$$ while $$\vert 1 \rangle$$ only occurs upon a successful query of the qubit oracle.

In line with this, the output produces a probabilistic distribution across all possible output permutations of the 5-qubit system, with a |0> bias. Since I am using the "amplitude amplification" method, or "reflection about the mean" the output value will generate a fluctuation in probabilities based on the solution to the problem presented. The fifth qubit Q4 is unused, and is reserved for problem encoding.

While IBM allows anyone to publicly access their 5 qubit processor, you will need to be upgraded to Expert User status to copy/paste the QASM code provided. Otherwise, as a Standard User you can build this same algorithm by following the drag and drop operations provided. I've already run this experiment on their live system using 4096 shots, as I do with all tests I run live.

I'd like feedback on suggestions of whether I need to keep the Q4 qubit reserved strictly for problem encoding, or if a problem would be more optimally encoded distributed across all qubits.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Whilst quantum computing is completely out of my competence, I'm very pleased to see this on Code Review, and I hope it attracts the attention of someone who can review it. I will note that QASM does appear to have support for comments, and like all low-level languages (particularly microprocessor assembly languages), it's a good idea to be extremely liberal with them! \$\endgroup\$ Jun 1, 2018 at 7:42
  • \$\begingroup\$ Maybe measurement itself is the issue, rather than necessary..... \$\endgroup\$
    – floor cat
    Jul 5, 2018 at 8:42

1 Answer 1

2
\$\begingroup\$

Now that IBM has upgraded their quantum processor, and further reflection on how to implement a Shor-Grover algorithm on what is available through IBM I believe this question is answered by saying there needs to be additional registers in order to implement any sort of problem to be solved by the algorithm.

If you implement the following code without measurement, you see the following areas are naturally encoded into the search space. Bear in mind the measurement is rotated through the search space. q-sphere output of algorithm

OPENQASM 2.0;
include "qelib1.inc";
gate nG0(param) q {
  h q;
}

gate nG1(param) q {
  h q;
}

gate nG2(param) q {
  h q;
}

gate nG3(param) q {
  h q;
}

gate nG4(param) q {
  h q;
}

qreg q[5];
creg c0[3];
creg c1[3];
creg c2[3];
creg c[7];

ccx q[0], q[1], q[2];
nG0(pi * 2) q[3];
y q[0];
ry(pi + 1) q[1];
cswap q[2], q[3], q[4];
cswap q[0], q[1], q[2];
cx q[3], q[4];
rz((pi * 2) + 1) q[2];
cy q[0], q[4];
rxx(21) q[3], q[4];

gate nG8(param) q {
  h q;
}

gate nG9(param) q {
  h q;
}

h q[0];
h q[1];
x q[2];
t q[3];
rz(pi / 2) q[4];
s q[0];
cx q[1], q[2];
s q[3];
cx q[0], q[2];
tdg q[3];
x q[0];
z q[1];
s q[2];
id q[3];
cx q[0], q[2];
tdg q[3];
h q[0];
cx q[1], q[2];
z q[3];
x q[0];
h q[1];
s q[3];
cx q[0], q[2];
rxx(pi / 2) q[3], q[4];
nG0(pi / 2) q[0];
h q[1];
tdg q[2];
cswap q[2], q[3], q[4];
cy q[2], q[3];
ccx q[0], q[1], q[2];
rz(pi / 2) q[3];
swap q[0], q[1];
nG0(pi / 2) q[2];
swap q[3], q[4];
rz(pi / 2) q[0];
rx(pi / 2) q[2];
ry(pi / 2) q[4];

The output with measurement results in $$|01000>$$ which aligns with a successful query. Encoding a problem requires additional registers, rather than integrating the operations into the search algorithm itself. Shor-Grover Measurement

\$\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.