Apollo 13 - Tao Liu's blog: 2019

Monday, September 2, 2019

6-Year-Old Rule?

The story begins recently I am indulging in the quantum computing programming whose foundation involves a lot of linear algebra. The direct consequence is I want to solve almost all problems using the complex number, vector, and matrix. The Mars Rover problem got my attention.

The rover on the Mars surface only takes L, R, and M instruction. L means turn left. R means turn right. M means move 1 step forward. If the initial position is (0, 0) and facing North, what will be the location and facing direction after receiving couples of instructions?

This is a perfect opportunity to practice my math, I thought. The direction and location are all complex numbers. I can manipulate numbers to make the code concise! I convert the L, R, and M instruction to complex number op:

turn left L is complex (0, 1) where the real part is 0 and the imaginary part is 1
turn right R is complex (0, -1)
move forward M is complex number (1, 0)

The new location and direction can be computed like the following:

new location += op.Real * Direction //L and R's real part is 0, so it does not move location
new direction *= op //M is 1, so it has no effect on the direction

It looks cool and code is concise. I avoided those unpleasant switch statements.

Everything looks satisfying until I realize those expensive multiply operations might be a performance problem. I wrote a simple solution using those switch statements. The simple solution doubled the code. However, the performance is 30+% faster than my "elegant" one!

I told my wife what was going on when I encountered her in the kitchen, with a little bit of frustration. She smiled and pointed my 6-year-old son. "If the solution can be understand by him, it must be faster." she said, "It requires a smaller brain so it runs faster."

Well, both algorithms are O(n). Maybe next time, I should think on the big O level.

Sunday, March 3, 2019

Old stuff: my first IEEE paper on Computational Intelligence

Before I finished my college, I managed to publish a paper on evolutionary computation (EC). The paper is on the encoding part. My next task is to use quantum to rewrite my algorithm. Well, there is a quantum genetic algorithm (QGA) there. However, I think with the latest decision on Q# and quantum algorithms. The paper link is here.

Saturday, January 19, 2019

Microsoft Q# Day 1: Qubit Collapsed

After going through the quantum linear algebra, I am going to see some quantum concept by using Q#.

The first one I want to prove is measurement will collapse the qubit. I will use the AssertProb to verify the value with probability. The pseudo code is listed below:

use H gate to set the qubit to superposition
check the probability to 1 equals 0.5 (50%)
measure the qubit
check the qubit equals the measured value equals to 1 (100%). The qubit collapsed.

the code listed below:

namespace Quantum.QSharpApplication2
{
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;
 open Microsoft.Quantum.Extensions.Convert;

    operation Operation1 () : Unit
    {
        body(...)
        {
            using (ancilla = Qubit())
   {
    H(ancilla);

    AssertProb([PauliZ], [ancilla], Zero, 0.5, "error", 1e-5);
    AssertProb([PauliZ], [ancilla], One, 0.5, "error", 1e-5);

    mutable gate = PauliZ;
    let mX = Measure([gate], [ancilla]);
    AssertProb([gate], [ancilla], mX, 1.0, "error", 1e-5);

    Message(ToStringD(mX == Zero ? 0. | 1.));

    Reset(ancilla);
   }
        }
    }
}

Pages