4 ms·

This result is only about one kind of quantum algorithm. I don't agree with the characterization of quantum computers as being more like hard drives. If anythi

This result is only about one kind of quantum algorithm. I don't agree with the characterization of quantum computers as being more like hard drives. If anything this result pushes in the opposite direction. Quantum algorithms work best when they use an extremely small amount of data; the complexity of querying data can give classical computers a foothold.

mjburgess 5y ago
I wasnt clear in the sense of "HDD" I was using; it wasnt about data volume. I mean that a quantum computer isn't strictly a CPU whose computational properties are the ones we are using when we compute stuff (ie., discrete switching of states). It is more like a device which holds state in a non-discrete manner, eg., like freezing water; or the physical structure of a hard-disk. So that if/when we use a quantum computer to "do anything" useful, it is actually useful not because it is a better CPU, but more, because it /holds state/ more usefully. Ie., its computational properties aren't the interesting ones; it's (continuous?) state representation properties are. That's the claim i'm asking about at least, it would helpful if a specialist had a response.
- feanaro 5y ago
  I think the identification of "discrete" with "computational" is not very useful. There is such a thing as an analogue computer after all.
  - mjburgess 5y ago
    We'd need to look at analogue computers in a lot of detail to figure out in what sense they count as computers. I am taking the computer science defintion, ie., a universal Turing machine. All computable functions are over discrete inputs and outputs. I suspect either (1) the sense of computer at-work in "analogue computer" might just be problem-relative, ie., it is just that someone uses this device to help them compute something; or (2) that analogue computers do compute computable functions (ie., their computation is discrete). I suspect it is the latter, ie., the output and input to an analogue computer is discrete. As I'm pretty sure there isnt any coherent sense of "computer" as defined for continuous "input".
- Strilanc 5y ago
  There are a lot of different ways of understanding what exactly it is that makes quantum computers more powerful. There isn't one simple clean answer. As a counterpoint to the "it's the bigger state space" idea, note that quantum computations over a polynomial number of qubits with a polynomial number of steps can be simulated by a classical computer using polynomial space (but not polynomial time). So the quantum state space isn't "intrinsically huge" or beyond-the-reach-of-classcal; at least not in that particular sense. Also note that every quantum state we will ever make will be generated by some tractable number of operations done with a tractable amount of precision. So the reachable in practice states are discrete and compressible into a tractable number of bits [the bits being a description of the operations used to produce them].

mjburgess 5y ago

I wasnt clear in the sense of "HDD" I was using; it wasnt about data volume. I mean that a quantum computer isn't strictly a CPU whose computational properties are the ones we are using when we compute stuff (ie., discrete switching of states). It is more like a device which holds state in a non-discrete manner, eg., like freezing water; or the physical structure of a hard-disk. So that if/when we use a quantum computer to "do anything" useful, it is actually useful not because it is a better CPU, but more, because it /holds state/ more usefully. Ie., its computational properties aren't the interesting ones; it's (continuous?) state representation properties are. That's the claim i'm asking about at least, it would helpful if a specialist had a response.

feanaro 5y ago
I think the identification of "discrete" with "computational" is not very useful. There is such a thing as an analogue computer after all.
- mjburgess 5y ago
  We'd need to look at analogue computers in a lot of detail to figure out in what sense they count as computers. I am taking the computer science defintion, ie., a universal Turing machine. All computable functions are over discrete inputs and outputs. I suspect either (1) the sense of computer at-work in "analogue computer" might just be problem-relative, ie., it is just that someone uses this device to help them compute something; or (2) that analogue computers do compute computable functions (ie., their computation is discrete). I suspect it is the latter, ie., the output and input to an analogue computer is discrete. As I'm pretty sure there isnt any coherent sense of "computer" as defined for continuous "input".
Strilanc 5y ago
There are a lot of different ways of understanding what exactly it is that makes quantum computers more powerful. There isn't one simple clean answer. As a counterpoint to the "it's the bigger state space" idea, note that quantum computations over a polynomial number of qubits with a polynomial number of steps can be simulated by a classical computer using polynomial space (but not polynomial time). So the quantum state space isn't "intrinsically huge" or beyond-the-reach-of-classcal; at least not in that particular sense. Also note that every quantum state we will ever make will be generated by some tractable number of operations done with a tractable amount of precision. So the reachable in practice states are discrete and compressible into a tractable number of bits [the bits being a description of the operations used to produce them].