Embedded Files
14.1.2 Conditional rotation after the phase estimation
The reason we do the conditional rotation after the phase estimation is that this is how we move the result of the calculation to the ancilla, so we can sample it later ignoring the other registers.
14.1.3 Shor’s Algorithm
Shor's algorithm is just quantum phase estimation in disguise, so it is a good baseline for resource estimation. It is a very different setting from the shallow-circuit algorithms we have seen in Module 3. The key resource requirements to run this algorithm are: (a) Coherence time must be long, since we need time to implement millions of gates in a sequence. (b) We need millions of physical qubits for error correction, although the corresponding logical qubits are much less. For error correction in the gate model, you may need as many as 1000 (some researchers say 4000) physical qubits for 1 logical qubit. The better the physical qubits the less of them you need. This is why researchers and companies are competing to create the "best" physical qubits, in various physical modalities (superconducting, trapped ions, etc..). Error correction is always needed (Threshold Theorem), so the less physical qubits required to achieve good error correction, the better.
Remember that two single-qubit gates and a two-qubit gate can be universal, so it is incorrect to need gates that simultaneously act on more than two qubits. Then we could factor numbers of millions of bits.
It is unclear exactly how many physical qubits we need for error correction, but as a rule of thumb, we need roughly quadratically more than logical qubits. To give an idea how logical qubits of an annealer needs more physical qubits to implement, it is due to the lack of connectivity. All the physical qubits are not interconnected and this is a limitation. Imagine your problem needs to connect 1 and 3 but there is no connection between them. Imagine qb1 is linked to qb5, and qb2 is linked to qb5 and qb3. You implement the required chain considering logical qb1 as qb1&qb5, logical qb3 is qb2&qb3.
In the gate model, the error connection requires a high number of redundant qubits.
14.2 Video of Quantum Matrix Inversion
14.2.1 Resource doubled for a non-Hermitian matrix
Imagine that you have a matrix A that is not Hermitian. This implies the number of qubits required approximately doubles.
14.2.2 Rejection Sampling
Ignoring warnings for the qubit quality required, you implement this algorithm on a current quantum computer, for instance, to invert a 4x4 Hermitian matrix A. You observe a very high success rate in rejection sampling. This means Preparing the target state for verification further increases the circuit depth, plus the gates of SWAP test would make it too noisy for this measure to be meaningful. The poor coherence time, noise, and two-qubit fidelity would make it unlikely for the rejection sampling to give the correct state.
14.2.3 Qubit number n means Precision of Phase Estimation
The “n” in red circle, or the number of qubits, of the following picture indicates the precision of phase estimation.
The picture is step 2 (quantum phase estimation) to solve matrix inversion problem. The other steps are
Step 1: state preparation
Step 3: Conditional rotation after QFT-1
Step 4: un-compute the eigenvalue register (to uncorrelated it)
Step 5: rejection sampling
14.3 Assignment of quantum matrix inversion
The HHL algorithm underlies many quantum machine learning protocols, but it is a highly nontrivial algorithm with lots of conditions. In this notebook, we implement the algorithm to gain a better understanding of how it works and when it works efficiently. The notebook is derived from the computational appendix of the paper Bayesian Deep Learning on a Quantum Computer. We restrict our attention to inverting a 2×2 matrix, following Pan et al.'s implementation [1] of the algorithm. The hyperlinks refer to 4 important references.
0.99518473+0.j, 0.09801714+0.j, 0. +0.j, 0. +0.j,
0. +0.j, 0. +0.j, 0. +0.j, 0. +0.j]
The efforts of three-day testing are finally rewarded successfully. The reason why the tests are so painful is that (1) I did not pay attention to the qubit number (q[0],q[1],q[2], and q[3] cannot be used in un-computing because it is the data register), (2) I didn’t master the meaning of those gates (Hadamard, CNOT, IBM U1 and U3 gates). As stated again and again, I need to make summarized table to pin down the input, results, and rules of these gates.
The following picture shows the circuits for one of the tests. The upper half of the picture is the regular circuits. The bottom half of the picture is for un-computing. Form the picture it is easy to see un-computing circuit has Hadamard gate, although in our test code, the Hadamard operations are commented out. Also, un-computing has no z-gate.
In the following test description, 0.995 really means 0.99518473. 0.098 really means 0.09801714. q0q2 indicates cx(q[0],q[2]), etc.
CONCLUSION. A few actions are necessary: (a) eliminate all Hadamard gates and z-gates, (b) change hhl.x(q[3]) to hhl.x[q[2]) in the “End of Inverse(Controlled-U0)” of the un-computing operation (this is vital!!! The effort to test whether change it to q0, q1, or q2 is a five-minute thing), and (c) eliminate the code line: hhl.cx(q[0], q[3]) because q[3] cannot be touched hence “Inverse (Controlled-U1)” of the un-computing operation is totally eliminated. Very unfortunately, 3-day efforts are concentrated to modify this code line instead of eliminate it. Here I keep this test log to alert future students or engineers that the following efforts of 41 tests are totally unnecessary.
Test 1. this is the best I can do so far, to have 0.09801714 in position 9 and 0.99518473 in position 10, but the values at two position needs a swap. IF ONLY I can swap the two positions!!!
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
Test 2. change the order of (q0,q2) and (q0,q3) to swap the two positions 9 & 10. While 0.098 stays at the correct position 10, 0.995 was moved to position 5 (not position 1 as before? there is a problem...)
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
Test 3. add (q0,q2) and (q2,q0) at the bottom moves 0.995 to position 6 and 0.098 to position 13
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
Test 4. if knock off two symmetrical (q0,q2) and (q2,q0) below and above (q0,q3) and (q3,q0),
the 0.995 stays at the correct position 9 but 0.098 moves to position 2
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
Test 5. In order to bring down 0.098 from position 2 to position 10, we add back (q0,q2) and (q2,q0) at the bottom, now 0.995 is at position 6 and 0.098 at position 7
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
Test 6. In order to bring down both to position 9 and 10 we swap the top (q0,q2) and (q2,q0) to the bottom. This bring 0.995 to position 14 and 0.098 to position 6. Not a good move. Let us back to previous situation and think of some other strategy
hhl.cx(q[0], q[3])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
---------------------
Test 7. add another (q0,q2) and (q2,q0) at the bottom. Now 0.995 is at position 6 and 0.098 at position 2
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
Test 8. After reviewing test2 and test 4 and trying to find their middle ground, I add (q2,q0) after the top (q0,q2) and (q2,q0). Result: 0.995 at position 10 (not the correct position 9) and 0.098 at position 5 (not the correct position 10)
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
Test 9. Use (q0,q2) instead of (q2,q0) get worse result: 0.995 at position 5 and 0.098 at position 2.
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[0], q[3])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
Test 10. Since several simplified tries cannot get us closer to the answer, let us try a modification from Test 1, i.e. just change the order of (q0,q3). The result is the 0.995 stays at the correct position 9 but 0.098 moves to position 2. This result is the same as Test 4. So, we really don’t need the second (q0q2q2q0) to reach this result.
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[0], q[3])
hhl.cx(q[3], q[0])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
Test 11. Since several simplified tries cannot get us closer to the answer, let us try a modification from Test 2, i.e. just change the order of (q0,q3). The result is 0.995 at position 5 and 0.098 at position 2, same as Test 4 and Test 10. So, we really don’t need the second (q0q2q2q0) to reach this result.
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
Test 12. So, let us start the variations of Test 1. First, what if we get rid of second (q2q0q0q2) in Test 1? The result is 0.995 at position 9 and 0.098 at position 5
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
Test 13. “Stripped” Test. Further to get rid of bottom (q2q0q0q2) of Test 12, the result is 0.995 at position 9 and 0.098 at position 6
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[3])
Test 14. Add bottom (q0q2q2q0) to Test 13. The result is 0.995 at position 9 and 0.098 at position 2, same as Test 4, 10, 11.
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
Test 15. Because Test 3 shows keep adding bottom (q0q2q2q0) will bring down 0.098, let’s try adding this to Test 14. The result is 0.995 at position 9 and 0.098 at position 5
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
Test 16. Keep adding bottom (q0q2q2q0) to test 15 bring 0.098 to position 6
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
Test 17. Keep adding 2 bottom (q0q2q2q0) to test 16 bring 0.098 to position 5 – not our expectation!
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
Test 18. Try another route by adding (q2q0q0q2) at the bottom to test 13. The resulting rule is: if you add even number of bottom (q2q0q0q2), 0.098 is at position 2. For odd number of bottom (q2q0q0q2), 0.098 is at position 5. At all times, 0.995 remains at correct position 9. For example, the following adds 2 (even) (q2q0q0q2) at the bottom which bring 0.098 to position 2.
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
Test 19. How about adding more (q2q0q0q2) at the top? Adding 2 more (q2q0q0q2) at the top of Test 13 (the “stripped” Test), brings 0.995 to position 6 (no longer in correct pos 9) and 0.098 to position 13. Maybe the conclusion is that bottom (q2q0q0q2)‘s stabilize 0.995 at pos 9 and top (q2q0q0q2)‘s stabilize 0.098 at pos 10? Later experiments show that conclusion is wrong.
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[3])
Test 20. Experiments shows adding ONE (q2q0q0q2) at the bottom is good to keep 0.098 at correct position 10, but 0.095 goes to position 5. (However, another test of adding one more bottom (q2q0q0q2) changes 0.098 to position 13, and 0.995 goes to position 2, which is not good (0.995 and 0.098 further apart)).
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
Test 21. Four top (q2q0q0q2)’s and one bottom (q2q0q0q2)’s results in 0.995 stays at correct position 9 but 0.098 at position 5. Compare Test 20 and 21, the rule seems to be: under the condition of ONE bottom (q2q0q0q2), keep adding even number of top (q2q0q0q2)’s you make 0.995 stays in the right position 9 and 0.098 go to position 5; keep adding odd number of top (q2q0q0q2)’s you make 0.098 stays in the right position 10 and 0.995 go to position 5. The truth is: all these rules are derived scientifically but in vain; but the fundamental middle (q3q0q0q3) is wrong since the data in q3 must not be touched. In the middle, single or “pure” (q0q2) should be used.
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
Test 22. Simplest Test: Restart tests from the simplest: q0q2 in the middle only. The result is: 0.098 is at the right position 10 while 0.995 is at position 13.
# Inverse(Controlled-U1)
hhl.cx(q[0], q[2])
Test 23. Add q2q0 at bottom to Test 22. The result is: 0.098 is at the right position 10 while 0.995 is at position 14, further away from the correct position 9.
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
Test 24. Add q2q0 at top to Test 23. The result is: 0.098 is at the position 14 and 0.995 is at position 10. Compare with the result of Test 23, this is a SWAP effect.
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
Test 25. Add q2q0 at bottom to Test 24. The result is: 0.098 is at the right position 10 while 0.995 is at position 14. The is the same result of Test 23. So, the adding more (q2002)s has no effect. Wrong direction.
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
Test 26. Restart the test from simplest test 22 (q0q2) by adding (q0q1) at bottom. The result shows more positions are contaminated. So q01 seems a poison.
hhl.cx(q[0], q[2])
hhl.cx(q[0], q[1])
Test 27. But what if we add this “poison” q01 at the top also? The result goes back to simplest test 22, i.e. poison around simplest test has no effect. Wrong direction.
hhl.cx(q[0], q[1])
hhl.cx(q[0], q[2])
hhl.cx(q[0], q[1])
Test 28. Restart the test from simplest test 22 (q0q2) by adding q2q0 to the top of Simplest test 22. The result is: 0.098 is at the position 13 and 0.995 is at position 10. Very similar to Test 24. But this gets us nowhere.
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
Test 29. What if we surround the middle (q0q2) with “poison” as in the best Test 1, like the following? The result contaminates more fields. A disaster.
hhl.cx(q[1], q[0])
hhl.cx(q[0], q[1])
hhl.cx(q[1], q[0])
hhl.cx(q[0], q[1])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[1], q[0])
hhl.cx(q[0], q[1])
Test 30. However, if you reverse the order of q1 and q0, and make the middle a pure q0q2 without q2q0 to pair it, then the poison exerts no contamination. The result is same as the simplest test!!!
hhl.cx(q[0], q[1])
hhl.cx(q[1], q[0])
hhl.cx(q[0], q[1])
hhl.cx(q[1], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[0], q[1])
hhl.cx(q[1], q[0])
Test 31. What if we use q12 instead of q01 and q21 instead of q10 in Test 30? The result contaminates more fields. A disaster.
hhl.cx(q[1], q[2])
hhl.cx(q[2], q[1])
hhl.cx(q[1], q[2])
hhl.cx(q[2], q[1])
hhl.cx(q[0], q[2])
hhl.cx(q[1], q[2])
hhl.cx(q[2], q[1])
Test 32. What if we swap q2 and q3 in Test 1? The result moves the 0.098 and 0.995 from positions 9 & 10 to positions 5&6.
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[3])
Test 33. Eliminate one top q3003, the result is: 0.995 at position 5 and 0.098 at position 9. Not a right direction.
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[3])
Test 34. Swap the order of q0 and q3 and swap the order of q0 and q2 from Test 32, the result is 0.995 at right position 9 but 0.098 at position 6.
hhl.cx(q[0], q[3])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[3], q[0])
Test 35. Keep the middle q02 “pure” by eliminate q20 in Test 34. The 0.995 stays at right position 9 but 0.098 move down to position 14. The is very promising but unfortunately still wrong.
hhl.cx(q[0], q[3])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[3])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[0], q[3])
hhl.cx(q[3], q[0])
Test 36 if we also keep q03 “pure” by eliminate q30 in Test 35. The 0.995 is at position 2 and 0.098 at position 9. Wrong direction.
hhl.cx(q[0], q[3])
hhl.cx(q[0], q[3])
hhl.cx(q[0], q[2])
hhl.cx(q[0], q[3])
Test 37. Further simplify Test 35 by eliminate top q03. The 0.995 is at position 13 but 0.098 at correct position 10. Same as simplest test 22, and test 27 if you change q3 to q1.
hhl.cx(q[0], q[3])
hhl.cx(q[0], q[2])
hhl.cx(q[0], q[3])
Test 38. Insert q20 to the pure q02 middle, results in the q1 contaminant effect.
hhl.cx(q[0], q[1])
hhl.cx(q[1], q[0])
hhl.cx(q[0], q[1])
hhl.cx(q[1], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[0], q[1])
hhl.cx(q[1], q[0])
Test 39. Use one pair q0330 at the top. 0.995 is at position 2 and 0.098 at position 9. Bad.
hhl.cx(q[0], q[3])
hhl.cx(q[3], q[0])
hhl.cx(q[0], q[2])
hhl.cx(q[0], q[3])
hhl.cx(q[3], q[0])
Test 40. Use q12 instead of q03 in Test 37. Same result as test 37. However, this is better because we should not touch data in q3.
hhl.cx(q[1], q[2])
hhl.cx(q[0], q[2])
hhl.cx(q[1], q[2])
Test 41. Use q12 as in Test 1. Results are contaminated. If use pure middle q02 without q20, contamination is less.
hhl.cx(q[1], q[2])
hhl.cx(q[2], q[1])
hhl.cx(q[1], q[2])
hhl.cx(q[2], q[1])
hhl.cx(q[0], q[2])
hhl.cx(q[2], q[0])
hhl.cx(q[1], q[2])
hhl.cx(q[2], q[1])
14.3.7 Measuring 1 in the ancilla
At this point, if we measure 1 in the ancilla (qubit 0), the state will be proportional to
# Target state preparation
hhl.rz(-π, q[4])
hhl.u1(π, q[4])
hhl.h(q[4])
hhl.ry(-0.9311623288419387, q[4])
hhl.rz(π, q[4])
# Swap test
hhl.h(q[5])
hhl.cx(q[4], q[3])
hhl.ccx(q[5], q[3], q[4])
hhl.cx(q[4], q[3])
hhl.h(q[5])
hhl.barrier(q)
hhl.measure(q[0], c[0])
hhl.measure(q[5], c[1])
def get_psuccess(counts):
'''Compute the success probability of the HHL protocol from the statistics
:return: (float) The success probability.
'''
try:
succ_rotation_fail_swap = counts['11']
except KeyError:
succ_rotation_fail_swap = 0
try:
succ_rotation_succ_swap = counts['01']
except KeyError:
succ_rotation_succ_swap = 0
succ_rotation = succ_rotation_succ_swap + succ_rotation_fail_swap
try:
prob_swap_test_success = succ_rotation_succ_swap / succ_rotation
except ZeroDivisionError:
prob_swap_test_success = 0
return prob_swap_test_success
Page updated
Google Sites
Report abuse