Clear Text Example

Example 9. Consider the following sentences from "Scientific American":

A quantum computer can work on a superposition of many different inputs at once. For example, it could run an algorithm simultaneously on one million inputs, using only as many qubits as a conventional computer would need bits to run the algorithm once on a single input. Theorist have proved that algoritithms running on a quantum computer can solve certain problems faster(that is, in fewer computational steps) than any known algorithm running on a classical computer can. The problems include finding items in a database and factoring large numbers, which is of great interest for breaking secret codes.
The problem with the above sentence lies in text: Theorist have proved. How did they do that? How can they prove something about something that does not exist.
In order to see in more detail what the issues are let us study the following quoted subject:finding items in a database. This is still a very large subject. In order to narrow down this subject let us study the following example: count the number of letters in a sentence.

Implementation 1: Single processor

In order to write such a program we first have to define the following items of the database:
  1. a textstring which contains the sentence under investigation.
  2. an array of 26 items which contains the letters of the alphabet from A to Z. This we call the letterarray.
  3. an array of 26 items which contains the counts of the corresponding letter. This we call the countarray. Item 1 of countarray corresponds which item 1 of the letterarray i.e. the number of times the letter A is in the textstring.

The program we have to write consists of three parts: An outer loop, an inner loop and a small process.

  1. In the outerloop we calculate the letter from the textstring we want to count. This is called the textletter. We start with the first letter in the textstring until the last letter in the textstring.
  2. In the innerloop we calculate the letter from the alphabet (i.e. letterarray) with which we want to compare the textletter. This we call the alphabetletter. We start with item 1 from the letterarray untill item 26 from the letterarray.
  3. In the process part we basically do a comparison. We compare if the textletter is equal to the alphabetletter. When both are equal we increase the corresponding countarray, otherwise we do nothing.
    For the computer compare means to subtract two numbers and decide if the result is zero. The increase means to add 1 to an item in the countarray.
This shows the steps involved for a clasical computer to do this job.
For a quantum computer the steps are the same.
Select comments part 1

Implementation 2: Multi processor

The above program on a clasical process uses one processor.
In order to speed up the program you could implement the process part on 26 processors i.e. one processor for each letter. The program consists now of two parts: A loop and a process
  1. In the loop we calculate the letter from the textstring we want to count. This is called the textletter. We start with the first letter in the textstring until the last letter in the textstring.
  2. Start all the 26 processoren. All the processoren will now work in parallel
Each processor will do the following:
  1. In each processor we basically do a comparison. We compare if the textletter is equal to the letter that the processor is supposed to process. When both are equal we increase the corresponding countarray, otherwise we do nothing.
    Processor 1 will process the A, Processor 2 will process the B etc.
    Only one processor will find a match and update the count
This shows the steps how a clasical computer does this job when 26 processors can be used.
For a quantum computer the steps are the same. The quantum computer has to be modified compared with the first implementation.

Program Download

In order to get a copy select:CNTTEXT.BAS
In order to see the listing select:CNTTEXT.HTM
For operation select:CNTOPER.HTM

Reflection

The sentence under study starts with:A quantum computer can work on a superposition of many different inputs at once.
What is for sure is that: The article fails to explain what for a quantum computer the advantages are that its working is based on superpositions (including quantum teleportation and photon entanglement) in the sense that those concepts reduce the number of steps involved in performing a certain calculation.
The article fails to indentify exacly which part of a calculation a quantum computer can do faster. Does a quantum computer immediate know which word in the Encyclopedia Britannica you want to understand? I doubt that. Ofcourse if a quantum computer consist of as many of processors as there are words in the Encyclopedia than you can speed up your search. But the same is for a clasical computer. IMO assuming that there is a difference, than this difference must be much more subtle. The article fails to explain that.
The sentence under investigationstates that:Theorist have proved that algoritithms running on a quantum computer can solve certain problems faster etc
I hope that they do not mean 1%. The article fails because it does not give enough detail to prove there point. IMO the theorist are to quick in claiming this advantage.
Ofcourse if a quantum computer is smaller than a clasical computer than it can be faster. But that is not what the sentence under investigation claims: fewer computational steps are required. The article does not show a shred of evidence, to explain the details of this claim. As stated before concepts like: superpositions, quantum teleportation and photon entanglement do not support this claim.

Feedback

None

Comments part 1

There are three comments to make related to this program, which will speed up the calculation
  1. First you should not set the letters in alphabetical order in the letterarray but in order of most used letter first. Item 1 should contain the E.
  2. You can terminate the innerloop as soon as when you have found a match.
  3. You should include a seperate test in the outer loop to skip over all the characters which are not a letter from the alphabet.
All the above is true for both a clasical computer and the quantum computer.

Created: 6 June 2000
Modified: 26 October 2000
Back to my home page Index