Re: Quantum Computation

In article <d2h75b$od$1@xxxxxxxxxxxxxxx>,
Ralph Hartley <hartley@xxxxxxxxxxxxxxxx> wrote:
>
>Also, note that complexity is a property of *problems*, not algorithms,
>because there is no well defined way to say that two different machines
>are running the same algorithm.

Yes, complexity is a property of problems, in the context of
a particular computational model. But is is ALSO a property of
algorithms (in the same context), which allows you to analyse the
efficiency of them relative to the complexity of the problems.

Your last remark assumes that machines are being treated as black
boxes; this is sometimes the case in complexity analysis, but not
usually. It all comes down to what computational model you choose.

>> To a very good approximation, there is only one
>> practical problem that a quantum computer is known to solve
>> significantly faster than a deterministic one: integer
>> factorisation a.k.a. the discrete logarithm (Shor). Whether
>> there are any other problems that can be is an open question.
>
>That isn't quite true. There is another important class of problems for
>which Quantum Computing is better than classical, and it is a more
>appropriate topic for this list:
>
>Simulating quantum systems.
>
>Given a description of a quantum system, the problem is to answer
>questions about its behavior (Simple questions like "Is the probability
>to go from state A to state B in time t more than 0.5").
>
>You might not consider that a "practical" problem, but I would. I view
>anything that could be used to design a better transistor, or understand
>high temperature superconductivity etc. as practical. Quantum simulation
>wouldn't guarantee a solution to either problem, but it sure would help.

Now, I will dispute that. That is not a practical approach, on its
own. Before you can call it practical, you have to ensure that you
can both set up the required initial state and extract the information
you need from the final one. I know of several experts who believe
that those processes may be as expensive as the classical approaches.

Note that I am not saying that I think they are, but that they are
not known not to be. Actually, this one applies to factorisation as
well, to a great extent.

There is also the question of whether each problem will need a new
computer built from scratch, or whether there will be a way of
programming such state manipulations. Do you, or anyone reading this,
have any good references on that?


Regards,
Nick Maclaren.

.

Relevant Pages

  • Re: Innoivationm and the Curse of Knowledge, etc
    ... machines has shown me is biological machines ... I don't see the complexity in connecting two ... conditioning I believe was Dr. Grey Walter's ...
    (comp.ai.philosophy)
  • Re: Innoivationm and the Curse of Knowledge, etc
    ... machines has shown me is biological machines ... might learn to recognize "Wolf" as a stimulus. ... I don't see the complexity in connecting two ... conditioning I believe was Dr. Grey Walter's ...
    (comp.ai.philosophy)
  • Re: Size of RN vs USN (Was: Germany Still Loses BB...) [OFFTOPIC, BUT INTERESTING]
    ... >>That would be news to the cryptography world. ... algorithms exist which would solve these problems in polynomial time ... Sometimes it takes a lot of machines working together, ... there is this hype about quantum computes. ...
    (soc.history.war.world-war-ii)
  • Re: complexity of LP
    ... one must discern between the complexity in regards of step numbers ... An algorithm for solving linear programming problems in $O$ operations. ... On the worst case complexity of potential reduction algorithms for linear programming. ...
    (sci.math.num-analysis)
  • Re: What is complexity?
    ... >when describing molecules, and no matter what length of string you pick, I ... machines described on them... ... Consider a reference machine x. ... A measure for the complexity of x is: One averages the complexity of x ...
    (talk.origins)