For both a deterministic DM and a non-deterministic DM each to trully to be called random you have to include certain tests on the data.

>	One obvious difference is that we know how to build a deterministic machine with randomization (more-or-less), but we don't know how to build a non-deterministic machine.

To build a non-deterministic machine is very easy:

To have any use you have to consider your non-determistic DM and your deterministic DM completely separated. Which such a combination you can (in principle) do Monte Carlo type simulation and calculate pi. (However each time you get a different answer)

>

To explain the difference, let me very briefly describe a deterministic finite automata, a non-deterministic finite automata, and a randomized DFA. A DFA is a machine with a set of states and a set of transistions which tells how to move from state to state for each possible input. There is a single path from each state for each possible input.

What is you definition of single path?

>	A NFA can have multiple paths from a state for a single input symbol. The output of an NFA considers all possibilities that could be taken for the sequence of input symbols provided.

Difficult definition. Not easy to understand. What means considers Can you give an example ? Above you mention that we don't know how to build them so what is the point.

>	Note that a DFA can simulate an NFA by expanding its state space to be the power set of the state space of the NFA (i.e. the set of all subsets of the NFA state space). This has exponential cost in time and space, though.

>	A randomized DFA is just like a normal DFA except that when deciding what transistion to take from a state, it considers both the current input symbol and a randomly generated symbol. As a consequence, the output of the randomized DFA cannot be predicted from the input sequence.

Again what do you mean with: considers. How is that implemented.

>	Note that it's easy to get confused here, because the output of a non-deterministic machine on a specific input is deterministic.

Yes I'am confused. I would call the output non-deterministic.

>	However, the output of a randomized machine is non-deterministic.

It can also de deterministic if your randomized machine is deterministic. With a randomized deterministic machine when you calculate pi "each time" you get the same answer.

Nick.

https://www.nicvroom.be/ Select question 23
https://www.nicvroom.be/shor.htm

Robert Tucci wrote:

>	Ralph Hartley wrote:

>>	I am skeptical that a "quantum compiler" in your sense is practical, or even possible (depending on some definitions/assumptions).

>	I think you are unduly pessimistic.

...

>	A quantum compiler would be a practical solution to a practical, well defined problem.

A good program that did the job on a "best effort" basis would be a practical solution to a practical, well defined problem, but that's not what you asked for. You said "shortest".

>

there might be small subroutines in the program that required you to decompose a 2^5 dimensional unitary matrix into a SEO, and a quantum compiler would do this for you. We already know various algorithms for decomposing a unitary matrix into a SEO in a non-optimal way. Now we just have to find various optimizations that make these algorithms better,

All possible.

>	maybe at some point someone will provide a proof that we've improved them "as far as possible".

Not possible.

Give me the program, and I will construct a problem for which it can be improved more (assuming the program works on a large enough class of problems (i.e. unbounded memory etc.). If not, I will point out a class of problems it doesn't work on).

This is not specific to quantum computation. For any programming language, a compiler produces *a* SEO. "Optimizing" compilers try to produce a *better* SEO. None can always produce the *best*. All can be improved further (in principle, eventually it gets too hard). This is a theorem, so it isn't open to opinion (and is getting off topic for this list).

Ralph Hartley

In article , Nicolaas Vroom wrote:

>	"Kevin A. Scaldeferri" wrote

>>	In article <939044f.0303280253.1c4feb3d@posting.google.com>, Squark wrote:

>> >	kevin@inky.its.caltech.edu (Kevin A. Scaldeferri) wrote in message news:...

>> >>

In some crude sense, quantum computers are a little like non-deterministic machines. Now, it's not that hard to describe a non-deterministic algorithm in Lisp.

>>	You're confusing randomness with non-determinism. When discussing computability, those are very different things. A non-deterministic machine is not the same as a deterministic machine with randomization.

>	I do not understand and or it is not clear to me. IMO if you want to have a worthwhile discussion about determistic and non-deterministic you must first define what those concepts are. I will give you my definition, but anyone is allowed to disagree and come up with a better one.

No, no, no...

What I gave was not _my_ definition, nor am I interested in yours. The theory of computation has its definitions and it would be wise to conform to them. The definition of "non-deterministic" in this context does not imply randomness.

(Note that if non-deterministic was the opposite of deterministic, than the question of whether P=NP would be trivially false. It is only because non-deterministic machines are a superset of deterministic machines that the question makes any sense at all.)

>	A DM is called deterministic when if you repeat the same calculation with the same state of the Input Registers this results in the same state of the Output Registers. A DM is called non-determistic when this is not the case i.e. "each time" you get a different answer.

No, you should break yourself of this terminology if you want to communicate with other people interested in computability. In the standard terminology, both deterministic and non-deterministic machine produce the same output every time for a given input. Only a randomized machine can produce different output on repeated runs.

>>

To explain the difference, let me very briefly describe a deterministic finite automata, a non-deterministic finite automata, and a randomized DFA. A DFA is a machine with a set of states and a set of transistions which tells how to move from state to state for each possible input. There is a single path from each state for each possible input.

>	What is you definition of single path?

I mean that there is a transition function G : S x A -> S, where S is the state space and A is the symbol alphabet for the input.

>>	A NFA can have multiple paths from a state for a single input symbol. The output of an NFA considers all possibilities that could be taken for the sequence of input symbols provided.

>	Difficult definition. Not easy to understand. What means considers Can you give an example ?

The transition function of an NFA is G : S x A -> 2^S. An execution of an NFA succeeds if the intersection of the set of success sets with the output of the closure of G applied to the input string is non-empty.

Not sure if that was clearer. Honestly, you'd be best off to find a textbook or to do a web search to see the exact definitions.

>	Above you mention that we don't know how to build them so what is the point.

To understand the theory of computability.

>>	A randomized DFA is just like a normal DFA except that when deciding what transition to take from a state, it considers both the current input symbol and a randomly generated symbol. As a consequence, the output of the randomized DFA cannot be predicted from the input sequence.

>	Again what do you mean with: considers. How is that implemented.

I mean that the transition function is G : S x A x B -> S, where B is an alphabet of symbols which our source of randomness chooses from on each step.

>>	Note that it's easy to get confused here, because the output of a non-deterministic machine on a specific input is deterministic.

>	Yes I'am confused. I would call the output non-deterministic.

No, because it is always the same.

>>	However, the output of a randomized machine is non-deterministic.

>	It can also be deterministic if your randomized machine is deterministic.

One could consider degenerate cases where the randomness does not affect the output, but that's not very interesting, nor any more powerful than a normal deterministic machine.

>	With a randomized deterministic machine when you calculate pi "each time" you get the same answer.

No, generically a randomized algorithm would give different results each time, which are hopefully close enough or right often enough to be useful.

--
======================================================================
Kevin Scaldeferri			Calif. Institute of Technology
                      The INTJ's Prayer:
     Lord keep me open to others' ideas, WRONG though they may be.

In article , Gralp wrote:

>	Kevin A. Scaldeferri wrote

>>	You're confusing randomness with non-determinism. When discussing computability, those are very different things. A non-deterministic machine is not the same as a deterministic machine with randomization.

...

>>

A DFA is a machine with a set of states and a set of transistions which tells how to move from state to state for each possible input. There is a single path from each state for each possible input. A NFA can have multiple paths from a state for a single input symbol. The output of an NFA considers all possibilities that could be taken for the sequence of input symbols provided.

...

>	i'm affraid your definition of "non-deterministic" is somewhat different than just "not deterministic" which is anything that cannot be described by some semi-group law with unity (monoid).

Well, it's not _my_ definition, but you're correct that non-deterministic machines are not the complement of deterministic machines. That's what I was trying to explain. When we talk of "non-deterministic" in the context of computability, there is a very precise and limited sort of non-determinism that is allowed.

>

what about the deterministic systems with partial information accessible? if we cannot determine the initial conditions exactly, then the evolution will only be predictable to some extent with a probabilitic distribution of possible paths. according to your definition, this is non-deterministic model, but behaves like randomized deterministic one.

No, this is a completely different sort of problem. In the sorts of machines I'm talking about, the initial state is always uniquely defined, and the input is fully defined in advance of the execution of the machine.

To a limited degree, one could consider a NFA where the initial state is not fully determined, but is instead a set of states. If the initial set is fixed, then this is really no different that a normal NFA. If the initial state is variable, then you are really describing a family of machines, not a single machine.

>	is there a way to tell them apart? that is, to decide upon a record of outcomes, to which category the system belongs?

Well, as I said in my previous message, the output of both DFAs and NFAs are consistent for a fixed input. So, if you feed the same input into a machine multiple times (resetting the machine each time) and get different outputs, then you know that you are not dealing with one of these machines.

--
======================================================================
Kevin Scaldeferri			Calif. Institute of Technology
                      The INTJ's Prayer:
     Lord keep me open to others' ideas, WRONG though they may be.

Kevin A. Scaldeferri wrote:

>	You're confusing randomness with non-determinism. When discussing computability, those are very different things. A non-deterministic machine is not the same as a deterministic machine with randomization.

Actually, they're not very different. Every stochastic automaton has a non-deterministic automaton as its base:

a -- x -> b iff the probability of a transition from a to b on x > 0. a is an initial state iff the probability of a being an initial state > 0. b is a final state iff the probability of b being a final state > 0.

Some definitions of stochastic automata don't have any concept of final state. This can be treated as the limiting case of the more general definition (in which final states are allowed for) where all the final state probabilities go to 0.

So, there is a many-to-one correspondence between stochastic automata and non-deterministic automata.

In the setting of orthodox quantum physics (meaning, specifically: Schroedinger's Equation + Lueder's Rule), it's actually specifically a stochastic automaton that you have, not merely a non-deterministic; with the state transition probabilities given in the Lueder's Rule.

In article , Alfred Einstead wrote:

>	Kevin A. Scaldeferri wrote

>>	You're confusing randomness with non-determinism. When discussing computability, those are very different things. A non-deterministic machine is not the same as a deterministic machine with randomization.

>

Actually, they're not very different. Every stochastic automaton has a non-deterministic automaton as its base: a -- x -> b iff the probability of a transition from a to b on x > 0. a is an initial state iff the probability of a being an initial state > 0. b is a final state iff the probability of b being a final state > 0.

I'm pretty sure we're on the same side of this discussion, so let me try to clarify lest others become confused.

The definitions of a deterministic automaton, a non-deterministic automaton, and a stochastic automaton are quite similar. There is just a subtle difference in the transistion function(*) for each. Also, there are multiple equivalent definitions of each of the three.

_However_, stochastic automata are significantly different in what they do from deterministic or non-deterministic. Importantly, DFAs and NFAs are equivalent models of computation, while randomized automata are inequivalent to either.

(*) depending on the type of automata and the specific form of the definition, the "transition function" might not actually be a function. I'm not going to elaborate on that, though.

--
======================================================================
Kevin Scaldeferri			Calif. Institute of Technology
                      The INTJ's Prayer:
     Lord keep me open to others' ideas, WRONG though they may be.

Robert Tucci wrote:

>	I too believe quantum computers need something like a high level language and a compiler. My own, personal views about this are explained in http://www.ar-tiste.com/qubiter.html

At that URL you write: "Qubiter is a tool that translates this high level language to qubit level instructions which can then be fed to a QC."

Please can you give some imformation how you envision this last step ?

My first guess is that this is not simple, but ofcourse I can be wrong.

Can you use this methodology on any QC or are there special restrictions?

Suppose your QC consists of a set of Qbit registers. Does this last step means that you will initialize those Qbit registers with the correct values?

Suppose a problem requires a sequence of different quantum logical operations. Does Qubiter takes care that those operations are performed in the correct order on your QC?

When you use Qubiter does that mean that you can easily use the same QC to solve different problems?

Nick https://www.nicvroom.be/shor.htm

Nicolaas Vroom wrote in message news:<3EA19EC3.4B8A1B88@pandora.be>...

>	Please can you give some information how you envision this last step ?

To go from a quantum Bayesian Net to a SEO, one would follow a process like the one described in http://www.arxiv.org/abs/quant-ph/9805016 The process described in that paper is not yet implemented in Qubiter. At this point, all Qubiter does is to decompose a unitary matrix into a SEO, and this it can only do in an inefficient way.

>	Can you use this methodology on any QC or are there special restrictions?

You can use quantum Bayesian nets and quantum compilers to program any QC consisting of a finite number of qubits that are fairly free from interaction with the external environment so that their state can be modelled as a pure state instead of a mixed state. (Shor and Grover algorithms assume a pure state) Generalization of this programming method to systems in mixed states is probably possible but the theory for this hasn't been completely developed yet.

>	Suppose your QC consists of a set of Qbit registers. Does this last step means that you will initialize those Qbit registers with the correct values?

The output of a full, complete quantum compiler would be the SEO that you should apply to the QC PLUS also a description of the initial states that you should place the qubits in. Quantum Bayesian Nets contain (in their root nodes) information about initial conditions. This information must be translated into information about the initial conditions of the qubits.

>	Suppose a problem requires a sequence of different quantum logical operations. Does Qubiter takes care that those operations are performed in the correct order on your QC?

A bit unclear to me what you mean.

>	When you use Qubiter does that mean that you can easily use the same QC to solve different problems?

A bit unclear to me what you mean. I think a quantum compiler would allow us to program a QC to solve many problems that heretofore nobody knew how to program on a QC.

>	Nick https://www.nicvroom.be/shor.htm

Robert Tucci wrote:

>	Nicolaas Vroom wrote in message news:<3EA19EC3.4B8A1B88@pandora.be>...

> >	Please can you give some information how you envision this last step ?

SNIP

>	At this point, all Qubiter does is to decompose a unitary matrix into a SEO, and this it can only do in an inefficient way.

I understand

My question again to you is: "Qubiter is a tool that translates this high level language to qubit level instructions which can then be fed to a QC." Do you expect that this last step "fed to a QC" will ever be possible.

A classical computer consists of a CPU memory with data (registers) and memory (registers/bits) with instructions What a compiler does it initializes those instruction registers in a human friendly way.

A QC (My understanding) does not consists of instructions. It consists of a CPU (sort of) which contains a "matrix" Elementary Operations and data registers (Qubits)

In Nature vol 422 27 march 2003 at page 408 Rainer Blatt e.a. writes: " A QC can be BUILT using single qubit operations ('rotations') and two-qubit CNOT gates because any computation can be decomposed into a sequence of these basic gate operations." See articles 8 and 9 for detail.

I have written built in capital letters because that is how I understand how you have to use a QC in the future.

I expect that there is no direct programming involved.

You can use programming to decompose a computation, the output are like diagrams which can serve as blueprints to built a QC.

For examples of those diagrams see the pages 22-37 of: http://www.ccmr.cornell.edu/~mermin/qcomp/chap2.pdf

Nick https://www.nicvroom.be/shor.htm

In article <3EAA7B80.5DFF701E@pandora.be>, Nicolaas Vroom wrote:

>

My question again to you is: "Qubiter is a tool that translates this high level language to qubit level instructions which can then be fed to a QC." Do you expect that this last step "fed to a QC" will ever be possible. A classical computer consists of a CPU memory with data (registers) and memory (registers/bits) with instructions

I think that you are missing a crucial element, which is that "instructions" and "data" are not two seperate entities. This is of critical importance both theoretically, where it is central to concepts like universal machines and undecidibility, and practically, where it form the basis of powerful languages like Lisp and also enables a broad class of security breaches.

...

>	I have written built in capital letters because that is how I understand how you have to use a QC in the future. I expect that there is no direct programming involved. You can use programming to decompose a computation, the output are like diagrams which can serve as blueprints to built a QC.

No, it is possible (theoretically, at least) to build a universal quantum computer. One would be able to program such a beast in an analogous method to a universal classical computer.

--
======================================================================
Kevin Scaldeferri			Calif. Institute of Technology
                      The INTJ's Prayer:
     Lord keep me open to others' ideas, WRONG though they may be.

Nicolaas Vroom wrote:

>	What a compiler does it initializes those instruction registers in a human friendly way.

A compiler translates "high" level code to "low" level code. It generates a sequence of elementary operations, taken from a small basic set, for the hardware to follow. The output of what I call a quantum compiler is a sequence of CNOTs and qubit rotation instructions. QCs as currently envisioned will be able to perform these operations.

>	You can use programming to decompose a computation, the output are like diagrams which can serve as blueprints to built a QC.

These diagrams should not be understood as classical hardware circuit diagrams. They are more akin to classical flow charts.

Robert Tucci wrote:

>	Nicolaas Vroom wrote:

> >	What a compiler does it initializes those instruction registers in a human friendly way.

>	A compiler translates "high" level code to "low" level code. It generates a sequence of elementary operations, taken from a small basic set, for the hardware to follow.

First I explain in a simple way what instructions and what a compiler does. Consider the following program in pseudo code:

ML1 Load Reg1 with Memory Location 1000  Reg1 = "A"
ML2 Load Reg2 with Memory Location 1001  Reg2 = "B"
ML3 Load Reg3 with Memory Location 1002  Reg3 = "C"
ML4 ADD  Reg1 with Reg2   Result in Reg4  Reg4 = A+B
ML5 ADD  Reg4 with Reg3   Result in Reg4  Reg4 = A+B+C
ML6 Store Reg4 in Memory  Location 1003

Each instruction internally is stored as a string of bits. In Decimal Notation the program looks as something like:

	ML1 001 001  001000
	ML2 001 002  001001
	ML3 001 003  001002
	ML4 002 001 002 004
	ML5 002 004 003 004
	ML6 003 004  001003

>	The output of what I call a quantum compiler is a sequence of CNOTs and qubit rotation instructions.

Let me describe how I see such a program:

ML1 CNOT QB1 QB2 QB3
ML2 CNOT QB4 QB5 QB6
ML3 Rot  QB3  180
ML4 Rot  QB6  212
ML5 CNOT QB3 QB6 QB7

>	QCs as currently envisioned will be able to perform these operations.

I doubt that.

In Decimal Notation the program looks like
	ML1  0  1  2  3
	ML2  0  4  5  6		
	ML3  1  3  180
	ML4  1  6  212
	ML5  0  3  6  7
The first column is instruction type: 0=CNOT 1=Rotation

Is this what you have in mind ? Where are those instructions stored ? in Qubits Registers ? Do you agree that you need some sort of CPU to execute each instruction ? Does a QC has something what you call a Program Counter (PrC)? I doubt that

IMO if your QC wants to make use of concepts like: Superposition, Entanglement and or Parallel Processing than you cannot make use of instructions which are executed sequential under control of a PrC

> >	You can use programming to decompose a computation, the output are like diagrams which can serve as blueprints to built a QC.

>	These diagrams should not be understood as classical hardware circuit diagrams. They are more akin to classical flow charts.

Okay But still you have to use those flowcharts to BUILT a QC. The flowcharts only include CNOT's and Rotations. They don't include concepts like CPU, instructions and a PrC. At least that is my current understanding. Correct me if I'am wrong

Nick https://www.nicvroom.be/

Some poor soul not cited by Robert Tucci wrote:

>

Is this what you have in mind ? Where are those instructions stored ? in Qubits Registers ? Do you agree that you need some sort of CPU to execute each instruction ? Does a QC has something what you call a Program Counter (PrC)? I doubt that IMO if your QC wants to make use of concepts like: Superposition, Entanglement and or Parallel Processing than you cannot make use of instructions which are executed sequential under control of a PrC

Contrary to the von Neumann paradign, a QC would not store data and instructions in the same type of registers. A quantum computer CPU, as I understand it, would NOT store the program counter and instructions in quantum registers, but rather in classical registers.

The quantum registers (qubit arrays) would be loaded only with the initial data. These would be operated upon repeatedly until their quantum state, when measured, answered our question, within some degree of uncertainty.

>	The flowcharts only include CNOT's and Rotations. They don't include concepts like CPU, instructions and a PrC. At least that is my current understanding. Correct me if I'am wrong

yep. The qubit circuit diagrams do not tell you where instructions and program counters are stored, or how they evolve.

In article <3EB12AFE.DE009A42@pandora.be>, Nicolaas Vroom wrote:

>

First I explain in a simple way what instructions and what a compiler does. Consider the following program in pseudo code: ML1 Load Reg1 with Memory Location 1000 Reg1 = "A" ML2 Load Reg2 with Memory Location 1001 Reg2 = "B" ML3 Load Reg3 with Memory Location 1002 Reg3 = "C" ML4 ADD Reg1 with Reg2 Result in Reg4 Reg4 = A+B ML5 ADD Reg4 with Reg3 Result in Reg4 Reg4 = A+B+C ML6 Store Reg4 in Memory Location 1003 ML stands for Memory Location. The 6 instructions are stored in Memory Locations 1-6 The program contains three instuction types: 1 Load, 2 Add and 3 Store

...

>	Is this what you have in mind ? Where are those instructions stored ? in Qubits Registers ? Do you agree that you need some sort of CPU to execute each instruction ? Does a QC has something what you call a Program Counter (PrC)? I doubt that

I think you are fixating on a particular model of computation. However, it may or may not be useful to model quantum computation as a simple variation of this architecture.

As a somewhat wacky example for you to consider, a particular quantum compiler might produce "machine code" which consists of a sequence of bases (amino acids) and a sequence of NMR pulses to be applied to the protein.

Even in the classical realm, the van Neumann architecture is not mandated. People have built machines which implement the lambda calculus (Lisp) in hardware.

--
======================================================================
Kevin Scaldeferri			Calif. Institute of Technology
                      The INTJ's Prayer:
     Lord keep me open to others' ideas, WRONG though they may be.

Nick https://www.nicvroom.be/

In article , Nicolaas Vroom wrote:

>

Each different problem requires its own matrix or matrix of quantum logical gates. The question is: how do you take care that problem 1 will execute matrix 1 and problem 2 matrix 2. IMO you have to (re)built that matrix for each problem. Programming is no issue. It is a mechanical (engineering?) hardware oriented problem.

No, this is not true. It is known, in theory, how to construct a universal quantum turing machine. In other words, you can build a general-purpose quantum computer. You do not have to have a custom machine for each problem you want to solve.

There are several caveats and unknowns when it comes to building a QC in practice, but what you keep saying (that you can't build a general purpose QC) is false.

--
======================================================================
Kevin Scaldeferri			Calif. Institute of Technology
                      The INTJ's Prayer:
     Lord keep me open to others' ideas, WRONG though they may be.

"Kevin A. Scaldeferri" wrote:

>	In article <3EB12AFE.DE009A42@pandora.be>, Nicolaas Vroom wrote:

> >	Is this what you have in mind ? Where are those instructions stored ? in Qubits Registers ? Do you agree that you need some sort of CPU to execute each instruction ? Does a QC has something what you call a Program Counter (PrC)? I doubt that

>	I think you are fixating on a particular model of computation.

You should start with something in as much detail as possible and see what the consequences are.

>	As a somewhat wacky example for you to consider, a particular quantum compiler might produce "machine code" which consists of a sequence of bases (amino acids) and a sequence of NMR pulses to be applied to the protein.

Please let us start with the hardware platform (sort of) as described in Nature Vol 421 20 Feb 2003 page 823-825.

>	Even in the classical realm, the van Neumann architecture is not mandated. People have built machines which implement the lambda calculus (Lisp) in hardware.

Please let us first discuss "machine code" and what it means. IF machine code PrC and a CPU can be implemented on a QC than the next step to use a higher level is relative easy. However I have major doubts about the feasibility of the first part of that sentence making any discussion about the second part inappropiate.

Nick https://www.nicvroom.be/ can not be solved

In article , Nicolaas Vroom wrote:

>	"Kevin A. Scaldeferri" wrote:

>>	I think you are fixating on a particular model of computation.

>	You should start with something in as much detail as possible and see what the consequences are.

I think this is liable to cause you trouble. Classical and quantum computation are substantially different. You seem to want to start from a very detailed, specific architecture for classical computing and jump sideways to quantum computing. However, this architecture may be completely inappropriate for quantum computing.

>

>>	As a somewhat wacky example for you to consider, a particular quantum compiler might produce "machine code" which consists of a sequence of bases (amino acids) and a sequence of NMR pulses to be applied to the protein.

>	Please let us start with the hardware platform (sort of) as described in Nature Vol 421 20 Feb 2003 page 823-825.

I don't see why we should choose that platform over what I suggested. Both are proposed as ways to do quantum computation. No one knows whether either will scale to useful sizes.

People have actually successfully factored small numbers with Shor's algorithm using an NMR quantum computer. I don't believe any other approaches have actually done this.

>>	Even in the classical realm, the van Neumann architecture is not mandated. People have built machines which implement the lambda calculus (Lisp) in hardware.

>	Please let us first discuss "machine code" and what it means.

Machine code is whatever the machine executes. Different architectures can have machine codes that look completely different. That was my point. You can build a machine where the machine code is Lisp! It doesn't have to look at all like machine code for a van Neumann machine.

-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.

"Kevin A. Scaldeferri" wrote:

>	In article , Nicolaas Vroom wrote:

> >	"Kevin A. Scaldeferri" wrote:

> >>	I think you are fixating on a particular model of computation.

> >	You should start with something in as much detail as possible and see what the consequences are.

>	I think this is liable to cause you trouble. Classical and quantum computation are substantially different.

That is correct. Programming belongs to the realm of classical computation and that is why if someone believes that programming is also relevant for quantum computations he or she has to convince in as much detail as possible why and how it can be used. (and what the benefits are)

SNIP

>	People have actually successfully factored small numbers with Shor's algorithm using an NMR quantum computer. I don't believe any other approaches have actually done this.

That is correct. The following article in Nature discusses this subject. http://www.nature.com/nature/links/011220/011220-2.html Figure 1 shows a "Quantum circuit for Shor's algorithm" My interpretation of that figure is if you want to factorize larger numbers you have to increase the size of the circuit and you have to use more Qubits. The complexity more or less stays the same. My interpretation of the article is also that no programming is involved and programming is no issue.

> >	Please let us first discuss "machine code" and what it means.

>	Machine code is whatever the machine executes.

A classical machine

>	Different architectures can have machine codes that look completely different. That was my point. You can build a machine where the machine code is Lisp!

I fully agree for a classical machine. However the issue is quantum computers.

For a nice url about "NMR Quantum Information Processing" see: http://www.c3.lanl.gov/~knill/qip/nmrprhtml/nmrprhtml.html They do not mention programming.

The following url: "Three Lectures on Quantum Computing" http://beige.ucs.indiana.edu/M743-talk-2/M743-talk-2.html when you select "Introduction" there is a discussion in which the words: "High level language and LISP" are mentioned. However I do not think that it is any issue if you want to understand Quantum Computing and or if you want to built a Quantum Computer.

Nick https://www.nicvroom.be/shor.htm

In article <3ECE36A7.6FCF3D79@pandora.be>, Nicolaas Vroom wrote:

>	Programming belongs to the realm of classical computation and that is why if someone believes that programming is also relevant for quantum computations he or she has to convince in as much detail as possible why and how it can be used. (and what the benefits are)

This is getting rather tiresome, and this is going to be the last post I make on this thread.

Quantum computers can be "programmed" in principle. That is to say, it is known that you can construct a universal quantum computer. (For anyone not familiar with the lingo, crudely speaking, a universal computer is one that accepts a description of another computer (i.e. a program) and then simulates the behavior of that machine on the remainder of the input.) Anyone who is interested can do a web or literature search to find the details.

In practice, there may be many obstacles to this.

First, it's not clear that even special purpose quantum computers can scale to useful size.

Second, a universal machine is inevitable slower at any given task that a special purpose machine for that task. It may be that the loss of efficiency is such that in practice only special purpose quantum computers will be constructed and used.

Third, writing compilers for general high-level languages which target universal quantum computers in a way that actually takes advantage of the particular efficiencies of quantum machines may be too difficult a task.

Finally, there appears to be only a limited class of problems where quantum computers are algorithmically faster than classical computers. For the majority of computations, they do not give any algorithmic speedup and are expected to be significantly slower than classical computers. Therefore, many people suspect that only hybrid machines will be build, with a quantum computer as a subsystem of an otherwise classical computer. (This is, in spirit, somewhat akin to special purpose FPU, vector, or graphic chips in modern chip/board architectures.)

-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.

kevin@clyde.its.caltech.edu (Kevin A. Scaldeferri) writes:

>	People have actually successfully factored small numbers with Shor's algorithm using an NMR quantum computer.

Am I the only one who thinks that this is a bit exaggerated? Implementing about a dozen quantum gates for a seven qubit system is truly quite impressive, but real quantum factoring requires more than that, even for small numbers such as 15.

Hendrik Weimer

-- libquantum - Simulation of a Quantum Computer

http://www.enyo.de/libquantum/

"Nicolaas Vroom" wrote in message news:3ECE36A7.6FCF3D79@pandora.be...

>

That is correct. The following article in Nature discusses this subject. http://www.nature.com/nature/links/011220/011220-2.html Figure 1 shows a "Quantum circuit for Shor's algorithm" My interpretation of that figure is if you want to factorize larger numbers you have to increase the size of the circuit and you have to use more Qubits. The complexity more or less stays the same. My interpretation of the article is also that no programming is involved and programming is no issue.

My interpretation would be exactly the opposite. Namely, that the programming is more of a Hardware Description Language. This in itself is not necessarily a big step beyond standard software programming languages.

Dirk

"Hendrik Weimer" wrote in message news:86y90vtk32.fsf@gienah.enyo.de...

>	kevin@clyde.its.caltech.edu (Kevin A. Scaldeferri) writes:

> >	People have actually successfully factored small numbers with Shor's algorithm using an NMR quantum computer.

>	Am I the only one who thinks that this is a bit exaggerated? Implementing about a dozen quantum gates for a seven qubit system is truly quite impressive, but real quantum factoring requires more than that, even for small numbers such as 15.

Would 8 qubits be better, and less exaggerated? 10, 12... how many, in fact, before such a machine would be treated 'seriously'? It is proof of principle - no more. By the time we get to 100 qubit registers people will be claiming those 7 qubits were of major historical significance (assuming we get there). A matter of perspective, much like Babbage's machine that I could quite equally claim both didn't work and, had it worked, would be no match for a P4 running at 3GHz.

Anyway, the focus now seems to have shifted away from bulk NMR towards more normal semiconductor techniques using embedded atoms. Last I heard was that two atoms in a matrix had been entangled, which on the face of it is even less impressive.

However, it might just turn out to be a problem that can be 'cracked' in one breakthrough if we are very lucky. That entangling N (with N being a useful number) in such a system is a linear scaling in difficulty unlike the NMR method.

Dirk

"Dirk Bruere at Neopax" writes:

>	"Hendrik Weimer" wrote in message news:86y90vtk32.fsf@gienah.enyo.de...

> >	Implementing about a dozen quantum gates for a seven qubit system is truly quite impressive, but real quantum factoring requires more than that, even for small numbers such as 15.

>	Would 8 qubits be better, and less exaggerated? 10, 12... how many, in fact, before such a machine would be treated 'seriously'?

It is not a question of seriousness. But people tend to say that today's quantum computers are able to factorize small numbers, using a method that beats classical algorithms. And this is just not true.

>	It is proof of principle - no more.

Exactly. But the principle is controlling several qubits and applying gates on them. And this has been done before, although with less qubits and gates.

>	Anyway, the focus now seems to have shifted away from bulk NMR towards more normal semiconductor techniques using embedded atoms. Last I heard was that two atoms in a matrix had been entangled, which on the face of it is even less impressive.

The main problem is that we cannot easily say which technology is the best for building a scalable quantum computers. NMR devices do not seem to be very scalable, but it may be enough to actually do something useful with them.

As you said, other technologies such as ion traps seem to be much more promising. So I think that improvements in these areas are far more interesting even if they have already been realized in NMR devices several years ago.

Hendrik Weimer

-- libquantum - Simulation of a Quantum Computer

http://www.enyo.de/libquantum/

In article <86y90vtk32.fsf@gienah.enyo.de>, Hendrik Weimer wrote:

>	kevin@clyde.its.caltech.edu (Kevin A. Scaldeferri) writes:

>>	People have actually successfully factored small numbers with Shor's algorithm using an NMR quantum computer.

>	Am I the only one who thinks that this is a bit exaggerated? Implementing about a dozen quantum gates for a seven qubit system is truly quite impressive, but real quantum factoring requires more than that, even for small numbers such as 15.

Maybe you can elaborate? This article,

http://www.research.ibm.com/resources/news/20011219_quantum.shtml

(which is little more than a press release, I grant) states:

The IBM scientists controlled a vial of a billion-billion (10^18) of these molecules so they executed Shor's algorithm and correctly identified 3 and 5 as the factors of 15.

I.e., they designed and fabricated an appropriate molecule, then applied a specified series of NMR pulses to perform the factorization, then read out the results.

So, what do you consider the shortcoming here?

-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.

In article <86fzmwyjzu.fsf@gienah.enyo.de>, Hendrik Weimer wrote:

>	"Dirk Bruere at Neopax" writes:

>>	"Hendrik Weimer" wrote in message news:86y90vtk32.fsf@gienah.enyo.de...

>> >	Implementing about a dozen quantum gates for a seven qubit system is truly quite impressive, but real quantum factoring requires more than that, even for small numbers such as 15.

>>	Would 8 qubits be better, and less exaggerated? 10, 12... how many, in fact, before such a machine would be treated 'seriously'?

>	It is not a question of seriousness. But people tend to say that today's quantum computers are able to factorize small numbers, using a method that beats classical algorithms. And this is just not true.

Other than qualifications which should be added to the final clause (i.e. that this refers to the asymptotic complexity, not this particular case) I don't understand what isn't true.

Please clarify _exactly_ what you feel makes this example not qualify as an implementation of Shor's algorithm.

-- ====================================================================== Kevin Scaldeferri Calif. Institute of Technology The INTJ's Prayer: Lord keep me open to others' ideas, WRONG though they may be.

Nick https://www.nicvroom.be/

Nick https://www.nicvroom.be/

http://www.enyo.de/libquantum/

John Eastmond wrote:

>

I've seen quantum computers described by networks of quantum gates in a manner analogous to how classical computers are made up of boolean logic gates. However most people who work with classical computers are not concerned with their hardware but rather with the software that runs on it. I was wondering what computer language one would use to program quantum computers.

Based on my understanding of Quantum Computers QC you will "never" be able to program a quantum computer QC using a software program written in a computer language.
In order to use a QC in order to solve EACH particular problem you have to build your QC (the hardware) with the aid of building blocks (QuBits, and logic gates) completely.
A QC is very much like an Analog Computer AC. With an Analog Computer you run in the same problem:
1. You have to build (hardware configure using wires) you AC each time. (there are ways to ease this, by using special patch boards)
2. The more differential (difference) equations you have and the higher the order of each the more hardware in the form of integrators you need. (See also https://www.nicvroom.be/shor.htm )

In general with a Quantum Computer you have to be very much concerned with the hardware and not with the software.

What we need is a standard way to describe our problem, some form of CAD drawing, which we can give to the QC manufacturer in order for them to build our QC.

Nick.

Peter Shor wrote:

>

I don't know any physicists who share this view, but I wouldn't be surprised if there were some. Note that I'm not counting here the fairly large number of physicists who believe quantum computing won't happen not because it's fundamentally impossible but because it is too difficult an engineering problem.

My main concern is that QC maybe is impossible. To "solve" that issue I have the following overall question: Is quantum entanglement a necessary feature for a QC to work?

To answer that question lets us study the two articles in Nature identified as 7 and 8 in the following document: https://www.nicvroom.be/shor.htm In document 8
1. "Superposition is a one particle property."
2. "Entanglement is a characteristic of two or more particles."
IMO you can have a register of 13 Qubits with or without entanglement. The difference, if I interpret the documents correct, lies in the coupling i.e. without coupling no entanglement.

My more detailed question is entanglement of the 13 qubits required for Step 3 (Observe Register 2 for n=55 - See Document 1) Does Step 3 (Result of x^a Mod n) work when the qubits are in superposition ?

IMO Step 2 and Step 3 will also work when the 13 Qubits are in superposition. In document 7 this means each qubit is oscillating at his own frequency - with no interference between each qubit.
IMO when you measure Register 2 with or without entanglement you have the SAME chance of measuring any of the values:

The same question I have for the combination Step 4 and Step 5: Is entanglement of the 13 qubits required for the FFT to function properly? If the answer is Yes then what is the observed difference? Does it mean that only with entanglement you have a 4.4% chance of measuring 4915 and not with superposition ?

>	I do expect that if quantum computing is discovered to fail due to fundamental reasons, somebody will win a Nobel Prize for this discovery.

hum...

>	Peter Shor

Nick

"Kevin A. Scaldeferri" wrote:

>	In article , Nicolaas Vroom wrote:

> >	"Kevin A. Scaldeferri" wrote:

>

> >	I do not understand and or it is not clear to me. IMO if you want to have a worthwhile discussion about determistic and non-deterministic you must first define what those concepts are. I will give you my definition, but anyone is allowed to disagree and come up with a better one.

>	No, no, no... What I gave was not _my_ definition, nor am I interested in yours. The theory of computation has its definitions and it would be wise to conform to them. The definition of "non-deterministic" in this context does not imply randomness.

For a definition of Deterministic see: http://www.swif.uniba.it/lei/foldop/foldoc.cgi?deterministic
For a definition of Non-Determinism see: http://www.swif.uniba.it/lei/foldop/foldoc.cgi?non-determinism

IMO if your algorithm or methode tries all possible solutions than your methode should be called deterministic. And "ofcourse" every time you will get the same answer.

For a definition of "non-deterministic polynomial time" See: http://www.swif.uniba.it/lei/foldop/foldoc.cgi?non-deterministic+polynomial+time
Here they use the wording "trial and error" What does "trial and error" mean ?
If it means: try all possible solutions than again I would call this deterministic.
If it means: to use a random mumber generator than in order to get every time the same answer your random number generator should also every time generate the same number sequence.

The following shows "Non-deterministic Ada Programs" http://www.csc.liv.ac.uk/~ped/teachadmin/algor/cooks_thm.html
This is Cook's Theorem via: http://www.csc.liv.ac.uk/~ped/teachadmin/algor/comput.html
In that program they use a subroutine CHOOSE. The question is how does "choose" select between 0 and 1.
Randomly ? or by "Trail and Error" ?

>	(Note that if non-deterministic was the opposite of deterministic, than the question of whether P=NP would be trivially false. It is only because non-deterministic machines are a superset of deterministic machines that the question makes any sense at all.)

>

No, you should break yourself of this terminology if you want to communicate with other people interested in computability. In the standard terminology, both deterministic and non-deterministic machine produce the same output every time for a given input. Only a randomized machine can produce different output on repeated runs.

> >	Above you mention that we don't know how to build them so what is the point.

>	To understand the theory of computability.

However that is not the subject of this thread. The subject of this thread is: "I was wondering what computer language one would use to program quantum computers."

A digital computer you can program in machine language but that is very cumbersome and not very user friendly. A much more friendly way is to use a higher level language for example ADA or Visual Basic (And many others)

The Question is: can you use any of those higher level languages to program a quantum computer.

IMO you can try to use those programming languages to SIMULATE a quantum computer on a digital computer. For example I have used EXCELL to simulate shor's algorithm on a PC. A free copy is availble via my url. However IMO you can not use any of those computer language on a quantum computer.

A Quantum computer is very much identical as an Analog Computer: You can not program an Analog Computer. In order for an Analog Computer to solve a problem you more or less have to build your own Analog Computer out of a set of available hardware modules: Integrators, Summers, Multipliers, limiters, wiring cords etc.

For a quantum computer based on what I read the same situation exists: In order to solve a problem on a quantum computer you must have all the hardware (Qubits and all the Quantum gates, which perform the quantum operations) hardwired together.

An interesting question to answer is if it possible to simulate a Quantum Computer on an Analog Computer including superposition and entanglement. If the answer is confirmative than the chance of simulating a Quantum Computer on a Digital Computer is almost answered.

Nick https://www.nicvroom.be/ See question 23

"Kevin A. Scaldeferri" wrote:

>	In article <3EAA7B80.5DFF701E@pandora.be>, Nicolaas Vroom wrote:

> >	A classical computer consists of a CPU memory with data (registers) and memory (registers/bits) with instructions

>	I think that you are missing a crucial element, which is that "instructions" and "data" are not two seperate entities.

In my reply today to Robert Tucci I wrote in detail how a program line like:

An example in which one instruction is modified:

  ML1 Load Reg1 with Memory Location 5     Reg1 = instruction
  ML2 Load Reg2 with Memory Location 1000  Reg2 = "A"
  ML3 ADD  Reg1 with Reg2   Result in Reg4 Reg4 = instr + "A"
  ML4 Store Reg4 in  Memory Location 5
  ML5 Store Reg2 in  Memory Location 1000

Add the end of program execution:

When "A" = 0 nothing happens because ML5 is not modified
When "A" = 1 ML5 is modified into:
        ML5 Store Reg2 in  Memory Location 1001
        That means ML 1001 contains a 1
When "A" = 2       ML 1002 contains a 2
    etc

A more practical example in which instructions are modified is used by subroutine handling (return address) but that is not crucial and outside the scope of this thread.

>	This is of critical importance both theoretically, where it is central to concepts like universal machines and undecidibility, and practically, where it form the basis of powerful languages like Lisp and also enables a broad class of security breaches.

IMO this has "nothing" to do with QC's and with the subject of this thread in particular.

> >	I have written built in capital letters because that is how I understand how you have to use a QC in the future. I expect that there is no direct programming involved. You can use programming to decompose a computation, the output are like diagrams which can serve as blueprints to built a QC.

>	No, it is possible (theoretically, at least) to build a universal quantum computer. One would be able to program such a beast in an analogous method to a universal classical computer.

In my reply to Robert Tucci I have shown how I envision such a program. It looks something like:

	  ML1 CNOT QB1 QB2 QB3
        ML3 Rot  QB3  180
        ML5 CNOT QB3 QB6 QB7

In short I have great doubts that you can program a QC. That does not mean that you can not solve all types of problems on a QC.

Nick. https://www.nicvroom.be/

"Kevin A. Scaldeferri" wrote:

>	In article , Nicolaas Vroom wrote:

> >	Each different problem requires its own matrix or matrix of quantum logical gates. It is a mechanical (engineering?) hardware oriented problem.

>	No, this is not true. It is known, in theory, how to construct a universal quantum turing machine. In other words, you can build a general-purpose quantum computer. You do not have to have a custom machine for each problem you want to solve.

Please go to the following document and study the pages 23-25 http://www.ccmr.cornell.edu/~mermin/qcomp/chap3.pdf Page 23 shows figure 1, Page 24 shows figure 2 and Page 25 shows figure 3 Each of those figures shows a different circuit diagram to implement the same problem or functionality.
i.e. for input qubits x0-x3 on the right side
i.e. for output qubits y0-y3 on the left side
i.e. and a matrix in between
That means figure 1 shows matrix 1, figure 2 matrix 2 and figure 3 matrix 3.

The question is how do you physical implement those three circuits in a general purpose QC.

IMO each matrix has to be built separately that means you need 3 QC's to solve those three implementations (in order to demonstrate all three problems in quick succession )

In principle you can also implement those three circuits in one QC in order to multi use the same input registers x0-x3 and y0-y3 however the matrix of that QC is larger than the sum of matrix 1 plus matrix 2 plus matrix 3, because you need additional selection logic.

If there is a fourth circuit than you must "rebuilt" your matrix and make it larger with matrix 4

>	There are several caveats and unknowns when it comes to building a QC in practice, but what you keep saying (that you can't build a general purpose QC) is false.

Part of this discussion depents on definitions. A special purpose QC is a QC which only can solve one particular problem A general purpose QC is a QC which allows you to solve different problems.
The question of course is what is the physical difference between a spQC and a gpQC i.e. what is it that a gpQC has more, as what a spQC does not have.

If you can give me some hints what those physical differences are than I will be very gratefull.

A PC is a general purpose computer. Each of those figures and circuits requires a separate program (which contains 4 lines of coding) Performing the functionality of figure 1 or circuit 1 means loading program 1 and excuting program 1 etc etc.

Nick https://www.nicvroom.be/

Created: 26 Maart 2003
Last updated: 29 April 2003

Back to my home page Contents of This Document