Re: Next generation COBOL?


"Steve Richfie1d" <Steve@xxxxxxxxxxxxxxxxxxxxx> wrote in message
news:3uqhohF12lnkiU1@xxxxxxxxxxxxxxxxx
> Herwig,
>
> I attended a talk and had some discussions afterwards with a group who was
> working on a quantum computer for the NSA. The question came up: Immediate
> problems aside, what COULD quantum computers potentially do for us better
> than conventional computers?
>
> The only apparent answer seemed to be factoring large numbers for crypto
> applications, which rather limits the number of potential sales to the
> number of countries. While there are a LOT of other conceivable
> applications, they all fail because either the setup would be impossibly
> difficult or because conventional computers are fast enough, or there is
> some other computational technology (e.g. analog) that would work well.
>
> However, perhaps you know some way past this logjam to be able to
> construct practical future quantum computers to solve real-world problems?

Computer scientists have classified problems by how hard they are to
solve. One such class is called "P" (for "Polynomial Time"), and problems in
P are essentially the hardest problems that the computers we have can solve
in a reasonable amount of time (sorting a list of numbers in in P, for
example). There exists also a different class, usually called EXP-TIME, for
"Exponential Time", and these are the sort of monstrous problems which we
essentially have no hope of ever solving, even if we let our most powerful
computers chug away at for the age of the universe. They are simply too
complex.

There's a class called "NP" which stands for "Nonderteministic
Polynomial Time", and we cannot solve them in a reasonable amount of time
with traditional computers, but we could solve them if we had Quantum
computers.

One classic NP problem is called "Travelling Salesman". The problem is,
given a list of cities with paths between them of given lengths, what is the
most efficient order to visit the cities in so that the Salemans (who has to
visit every city at least once) can spend the least amount of gasoline?

Airlines would probably love to have a way to solve this problem, as
then they could generate the best possible routes for airplanes to fly to
maximize profits.

There's a list of NP problems at:
http://www.nada.kth.se/~viggo/problemlist/compendium.html

though the descriptions of the problems are fairly abstract, and you
probably have to be relatively strong in mathematics to fully understand
them, and figure out where and how they might be useful in "real life". For
example, Travelling Salesman is at:

http://www.nada.kth.se/~viggo/wwwcompendium/node104.html

And the description is...

<quote>
# INSTANCE: Set C of m cities, distances $d(c_i,c_j)\in N$ for each pair of
cities $c_i,c_j\in C$.

# SOLUTION: A tour of C, i.e., a permutation $\pi: [1..m]\rightarrow[1..m]$.

# MEASURE: The length of the tour, i.e.,
$d\left(\{c_{\pi(m)},c_{\pi(1)}\}\right)+\displaystyle\sum\limits_{i=1}^{m-1}
d\left(\{c_{\pi(i)},c_{\pi(i+1)}\}\right)$.
</quote>

.... which didn't make the thought "Of course! Plane routing!" jump into my
head.

Still, you might be able to infer how the solutions might be used from
the name of the problems (e.g. some of them have the words "networking" or
"compression" in their names.)

- Oliver


.

Relevant Pages

  • Re: Next generation COBOL?
    ... Immediate problems aside, what COULD quantum computers potentially do for us better than conventional computers? ... algorithms which do not deal with QuBits. ... A problem not shared by programming languages. ...
    (comp.lang.cobol)
  • Rasetti: Quantum Computers based on TQFT
    ... QC can solve problems which are not in P in polynomial time. ... So the idea is that there may be more types of quantum computers than ... in as much we want to regard analog computers as computers when it ...
    (sci.physics.research)
  • Re: Rasetti: Quantum Computers based on TQFT
    ... > new and more powerful types of quantum computers. ... > polynomials is not in P. ... Analog computers tend not to work on hard problems, or when they do, ...
    (sci.physics.research)
  • Re: Incompleteness vs. Mechanical Reasoning
    ... perfectly possible future computers have free will in this sense. ... to assert that a computer's future action (e.g. will it halt or not ... NAFL, in which I have formulated my definition of free will. ... are quantum computers as defined via the NAFL model of computation ...
    (sci.logic)
  • Re: *Quantum Computing* expert Bill Munro
    ... these researchers called on scientists around the world to ... ]develop ciphers resistant to attack by quantum computers. ... Advances in mathematics can always destroy cyphers-- public or private ...
    (sci.crypt)