Quantum Computer

[bored]

I welcome our new ContractorUK quantum nutter!

[heinz]

Turing MAchine

Penrose would say that a Turing Machine could not 'discover' a new theory and cites Gödel Incompleteness Result to prove it. This is disputed though. For example, would a computer be able to 'discover' integration or the Pythagoras Theorem? Are we humans special in that only 'we' could do it, or could a machine do the same thing? I personally believe a computer could do it, but it would need to be a quantum computer to have the necessary power.

[TimberWolf]

Penrose would say that a Turing Machine could not 'discover' a new theory and cites Gödel Incompleteness Result to prove it. This is disputed though. For example, would a computer be able to 'discover' integration or the Pythagoras Theorem? Are we humans special in that only 'we' could do it, or could a machine do the same thing? I personally believe a computer could do it, but it would need to be a quantum computer to have the necessary power.

Yes, a computer could discover those, and in fact in the past I have written a program that could do just that. It could find Pythagoras theorem and solutions to many other polynomial time problems in a matter of minutes. What it couldn't do, it seems, is find polynomial time solutions to NP hard problems, just as we humans can’t. And just as the human brain is slow at solving them exactly; all approximate.

As far as I understand it, a quantum computer is no more powerful than a classical one, in the sense of it being able to calculate something a Turing machine could never manage. It may be faster at some problems, just as a massively parallel machine or DNA computer, etc may be, but all are thought able to be simulated by a Turing machine, i.e. your home PC and basic programming constructs such as loop, iteration and store. This I believe is open to conjecture, and vaugely recall (and may be wrong) that the question itself (whether a quantum computer or a classical one could solve NP complete problems in polynomial time) is itself NP complete, and may never be known.

[heinz]

Quantum Turing Machine

NP-hard problems, such as the 'subset sum problem', or Travelling Salesman Problem (TSP) where n is large have lengthy solutions for a Turing Machine since n can be arbitarily set at a high value.
Assume that the whole Universe were made into a Turing computer to solve a cryptographical subset sum problem such that every atom were made into a computer register then the value of n could still be set too high for the problem to be solved in a practically appropriate time span.

But such a monstrous computer (the size of the Universe!) would be the equivalent of a Q computer with just one little tiny 40 qubit register. Role on Q Computers eh?
I am wondering if a Q computer could manage infinite parallel computing power?, since entangled particles can have an infinite number of values (Heisenberg etc) all deriving from just one particle. For example, one fixed frequency photon has an exactly known momentum and therefore its position is completely unknown, and could be any. Its position would then provide our bit value range (infinity). This computer would not need all the atoms in the Universe to solve NP-Hard problems, one photon could do it. (oh no, I'm going
mad now, somebody correct me pls!)

The other interesting question is - could a computer come up with NP-Complete theory itself?
Evolution of life was a process that required and appears to have a direction too. Time and it seems quantum processing was necessary here to evaluate DNA outcomes or 'try-outs' as normal stochastic processes would not have been fast enough to achieve the biological sophistication we have today starting from a few carbon compounds.
In the same way, I believe, maths theorums themselves need an evolutionary process to appear in the Universe. Epistemological entities have a 'time' and direction dimension it seems.
In other words maths thoeries cannot just appear from basic axioms and operators just as humans cannot just appear from random collisions between atoms (the Universe is too small, although the math would say a random process could produce a human in one go because probabilities
can be set as small as required)

[TimberWolf]

The other interesting question is - could a computer come up with NP-Complete theory itself?

Since we don’t know whether P=NP, we might as well enlist the help of some sort of computer so that it can fail miserably too If we are smart enough to build one that is. One-way functions would presumably be easy enough for a computer to search for (a series of mathematical or algorithmic operations and an inverse not readily found), so I think computers could find hard examples just as we can. That isn’t a theory, but then we don’t know whether one-way functions exist either. We give ourselves too much credit for little I think, and Penrose not least.

Incidentally here’s a physical analogue of factoring a number n: Squash n frictionless spheres (or circles) into a rectangle. Keep squishing (and keeping the rectangle sides parallel) until there are no gaps left inside. The length of the sides gives the integer factors.

Evolution of life was a process that required and appears to have a direction too. Time and it seems quantum processing was necessary here to evaluate DNA outcomes or 'try-outs' as normal stochastic processes would not have been fast enough to achieve the biological sophistication we have today starting from a few carbon compounds.
In the same way, I believe, maths theorums themselves need an evolutionary process to appear in the Universe. Epistemological entities have a 'time' and direction dimension it seems.
In other words maths thoeries cannot just appear from basic axioms and operators just as humans cannot just appear from random collisions between atoms (the Universe is too small, although the math would say a random process could produce a human in one go because probabilities
can be set as small as required)

There is a simpler unsatisfactory explanation of life the universe and everything, and that is if the universe were not just the way it is we just wouldn’t be here to notice.

Life developed early on Earth and since most of our ancestors were single celled for most of the time, it seems that evolution had a harder time becoming multi-cellular than starting-out. Once multi-cellular creatures arose, biological sophistication came very fast.

[PerlOfWisdom]

I am wondering if a Q computer could manage infinite parallel computing power?, since entangled particles can have an infinite number of values (Heisenberg etc) all deriving from just one particle. For example, one fixed frequency photon has an exactly known momentum and therefore its position is completely unknown, and could be any. Its position would then provide our bit value range (infinity). This computer would not need all the atoms in the Universe to solve NP-Hard problems, one photon could do it. (oh no, I'm going
mad now, somebody correct me pls!)

Well I can provide a photon if that helps. Well when I can get some AA batteries.

[PerlOfWisdom]

Don't stint yourself.

Have a couple, you never know when a spare might come in handy. Like.

I like stinting myself.