In the post, we are discussing “Corrigan-Gibbs, H., Wu, D. J., & Boneh, D. (2017, May). Quantum operating systems. In Proceedings of the 16th Workshop on Hot Topics in Operating Systems (pp. 76-81). ACM.”.

Problem

Many researches have been working on new quantum computers, however, no one ever propose an operating system for it. Therefore, this paper tries to answer the following quetions:

• What abstractions could a quantum os expose to the programmer?
• How could the power of quantum computers improve the performance?
• What would a distributed sytem of quantum computers look like?

Solution

Quantum systems cak solve the unstructured search problem fast. Normally, it checks N inputs to determine the result while quantum computers checks only a square of N to know the answer.

Method

• The paper presents qthread, which is simliar to pthread; programmers can create a qthread and it will conduct classical computation. What makes qthread different is the join functions. Quantum systems can answer questions like which qthread returns an non-zero value very fast.
• The paper gives four example applications to use the power of quantum computing.
  • Most Interesting Job First (MIJF) Scheduler: Reduce the scheduling complexity from N to a square root of N in order to find the most interesting task.
  • Edit distance problem: Useful in biology when looking for the gene matches and quantum computers can find the best match very quickly.
  • Map Reduce: Quantum computers can perform a much faster reduce function.
  • Unit Testing: Less cases (a suqare roof of N) to run to achieve the same coverage of N cases on a classical computer.
• Prehsared information allows clients and servers transmit at a double rate.

  Takeaway

• It’s speculative.
• Sequential algorithms can reduce its time complexity to a square root of N.
• Entangled bits can double the transmit rates.

Get the presentation here.