17
$\begingroup$

I understand what a qubit-based quantum computer by the current definition is and how they are constructed. I read another thread where someone suggested encoding a computation into a dual-slit experiment and reading out the answer as interference vs non-interference, and this was mostly shot down since it's not "useful", because the system ceased to be a quantum computer when decoherence occurred.

But this reminded me of an old idea I had on other ways to encode computations in physics than the "classical" qubit-based schemes. As a striking example, consider one of the canonical uses for a quantum-computer - to efficiently simulate quantum-level systems. Well - to do this without a quantum-computer, you could actually assemble the system itself and let it "run", and then read out what you were looking for to simulate in the first place in many cases, in a vastly more simple way than digitally calculating it with qubits. Is this then not also a "quantum computation", really? The closest analogue I can come up with is the way analog computers were designed before digital computers took over, and that they were indeed much more efficient at a certain class of problems.

Even a system of 3 particles performs a calculation (of sorts) which is difficult to simulate traditionally.

More generally, if you could encode your problem into a hamiltonian which you subsequently map onto a physical structure wouldn't this be very useful? You might not be able to run algorithms on it, but you might be able to format the problems the algorithms were meant to solve in the first place. I'd be interested in hearing if this approach is pursued and I have missed it or if it is deemed to be useless for some reason, or if it's useful but "digital" quantum computation is simply more attractive in the long-run so most of the focus is on that. Maybe there is a measure on the computational complexity that can be mapped or performed by a general quantum structure (non-qubit-based)?

I seem to remember a Canadian company called D-Wave which I think do this more or less, and there was (is) much heated discussions on if it was "real quantum computation" or not.

EDIT: Nature published a special Nature Insight review on this in April 2012, especially about Quantum Simulators, where the issues I brought up in this question are discussed, including the "digital vs analog quantum computation" issue.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ I'm not sure what "digital" quantum computation is. Aren't all quantum computers "analog" by definition, in that they abide by your description of a system in which you could encode your problem into a hamiltonian which you subsequently map onto a physical structure? This is how QC generally works. $\endgroup$
    – user346
    Commented Apr 7, 2011 at 3:53
  • $\begingroup$ @Deepak: Yes if by problem we mean how to map a QC algorithm. But like with digital computing this must form a pretty narrow subset of all possible information-processing methods on top of the selected "hardware". Digital computers are so simple to design in relationship to the difficulty of encoding problems onto analog electronics that the tradeoff was obvious >50 years ago. But for QC this relationship seems not so obvious (currently!), hence my curiosity. $\endgroup$
    – BjornW
    Commented Apr 7, 2011 at 9:59
  • $\begingroup$ Very nice question. Let me correct one thing; this isn't exactly what D-Wave does, and it isn't the issue in the heated discussion of whether or not D-Wave is building a real quantum computer. $\endgroup$
    – Peter Shor
    Commented Apr 7, 2011 at 16:03
  • $\begingroup$ @Peter: I remember now that what D-Wave did was settle a system in a ground-state, then change the hamiltonian into the problem-mapping one slowly enough that the system supposedly settles into the (new) problem-solving ground-state according to the adiabatic theorem. I guess this could be fuel for a separate Question.. $\endgroup$
    – BjornW
    Commented Apr 7, 2011 at 22:52

3 Answers 3

Reset to default
19
$\begingroup$

It's been proposed, and there are a variety of possible experimental systems people are working on. I expect this to be a very useful way of simulating quantum systems, which will work well for many questions long before large-scale universal quantum computers can be built.

Improve this answer
$\endgroup$
3
  • $\begingroup$ a very useful review paper. I think, however, that, as a discussion of simulating quantum mechanical systems with other quantum mechanical systems, it doesn't very directly address the Question, which I think asks about classical simulation of quantum computation. [Also, if you know of another citation that's open source, that would be good for some people here. I found a brief posting connected with one of the authors at rikenresearch.riken.jp/eng/research/6119, which gives a small feeling for the Science paper.] $\endgroup$
    – Peter Morgan
    Commented Apr 7, 2011 at 15:37
  • 1
    $\begingroup$ There's a non-paywalled version of the review article here. Also, I seem to have a different understanding of the Question than you do; it seems to me that the work surveyed in this paper is exactly what Bjorn is asking about. $\endgroup$
    – Peter Shor
    Commented Apr 7, 2011 at 16:08
  • $\begingroup$ It seems like a very nice review paper! Indeed it was something like this I was thinking should exist - and it seems like as always, Feynman mentioned it long ago ;) @PeterM: I was asking about ways to improve upon classical computation using quantum structures other than the typical qubit-computer. I guess this would include both using classical fields as well as pure quantum-systems. You both touch on interesting subjects but Peter Shor's article link was most closely related to my question I think. Thanks guys. $\endgroup$
    – BjornW
    Commented Apr 7, 2011 at 22:43
4
$\begingroup$

Well, i am just not sure that it would be useless, and just meant as an example (and not as a full answer to the more general aspects of your question), you could have super-FFT if you could encode the inputs of your FFT as dark/transparent pixels in a 2D light filter and then recover the FFT output as an 2D interference pattern with CCD. If this is actually scalable or interesting from a cost-benefit perspective its another, engineering-related matter.

This would of course be counted by many as a classical-analog computer, because it doesn't rely on entanglement of qubits, just good old wave huyghens interference

best FFT algorithms have complexities like $O( n \log(n^2) )$, so i don't know why no one has come up with an application for this yet. As i said, probably the reasons are entirely economical

Improve this answer
$\endgroup$
5
  • $\begingroup$ Nothing wrong with this, indeed I think it's a useful start, but I take this answer to rely on the mathematical order of a classical field being comparable to the mathematical order of the Schrodinger wave equation. Insofar as QM ultimately is about quantized fields, that structure is of a higher mathematical order than that of a classical field. Compare Wightman functions to the simplicity of a classical field on a manifold. To bring classical physics to the mathematical level of QFT, one has to introduce either probabilistic or stochastic methods over classical fields. $\endgroup$
    – Peter Morgan
    Commented Apr 6, 2011 at 22:29
  • $\begingroup$ @Peter: it seems to me that even a classical field possesses more information-processing power than for example the interaction of classical newtonish bodies. After all, to simulate the field using a classical computer requires much more processing power than to simulate (an ideal) billiard ball, and if you subscribe to the path-integral method, I guess you could say the classical field really requires the underlying interference of quantum paths to work. So in the context of my question, using a classical EM field to emulate an FFT is useful, even though not tapping the full potential of QFT. $\endgroup$
    – BjornW
    Commented Apr 7, 2011 at 10:10
  • $\begingroup$ @Bjorn Yes, classical field theory is computationally more powerful than a finite system of classical bodies. A field is, in a sense, infinite parallelism. Before I wrote my Answer to your Question, I had not focused on the significance of Monte Carlo methods; for some problems they are more effective/useful than trying to program some other algorithm. Stochasticity is relatively difficult to use, however, perhaps because of the often counter-intuitive nature of combinatorics and probability theory, so any help one can get bringing that under control is worthwhile. Qubits help. $\endgroup$
    – Peter Morgan
    Commented Apr 7, 2011 at 11:59
  • $\begingroup$ @Bjorn On the other hand, it may be that people think that Qubits help, but it's possible that more progress might be made if people just thought of quantum computing as sophisticated signal processing. That leaves open that more sophistication might be possible in how we process the analogue-with-more-or-less-discrete-features electrical signals that measurement apparatuses provide. $\endgroup$
    – Peter Morgan
    Commented Apr 7, 2011 at 12:10
  • $\begingroup$ However, i'm sure you guys are aware of this, but let me bring again to attention that even when creating a computation using some quasi-infinite degrees of freedom-system like a classical EM field in the example above, your useful computation is finite because the system bounded by resolution power/higher order diffraction terms/etc hence the pixels in the input (and in the output) are of finite size. I think this is what limits analog computing in general $\endgroup$
    – lurscher
    Commented Apr 7, 2011 at 15:08
3
$\begingroup$

The difference between a traditional analogue computer and a quantum computer is at least that the analogue computer is not stochastic (at least in concept; there's still noise, but the idea is to eliminate the noise as far as possible, not to use it). In particular, from the field theoretic perspective I usually work in, the mathematical structure of a classical field is of a lower order than the mathematical structure of a probability measure over values of a classical field.

If one goes to the higher order structure of probability measures over classical analogue structures instead of deterministic analogue structures, one is then close to the computational power of quantum mechanics. In particular, in a recent paper, "Equivalence of the Klein-Gordon random field and the complex Klein-Gordon quantum field", EPL 87 (2009) 31002, arXiv:0905.1263v2, I show that a quantized complex Klein-Gordon field is empirically equivalent to a real Klein-Gordon random field, which is essentially at the mathematical level of probability measures over classical fields. The traditional Klein-Gordon field, with no stochastic or probabilistic structure, however, is not of the same mathematical order.

More generally, a classical stochastic model can be presented in a Koopman-von Neumann formalism, which essentially just applies Hilbert space mathematics to classical probabilities. To return to the parenthesis of my first paragraph, for a classical analogue computer to approach the effectiveness of a quantum computer, my intuition (without enough justification) is that it would have to use some kind of noise in an essential way to improve the effectiveness of an algorithm. It may or may not be significant that Monte Carlo methods are a well-known example.

The real crux, however, is that a quantum mechanical way of thinking about the experimental apparatuses that are currently being used to push forward quantum computing as a technology, essentially in terms of qubits and closely similar finite-dimensional Hilbert space mathematics, is more productive than thinking in terms of classical stochastic signal processing, even though the concept of incompatible measurements is as natural in the classical mathematics of processing stochastic analogue signals as it is in quantum theory. [You go a long way towards providing this reason in your Question.] The particular advantage, as far as I can tell from outside the field, is that the mathematics of Hilbert spaces allows a quasi-digital way of algebraic thinking that bridges the gap between analogue and digital thinking more effectively than thinking just in terms of probability measures over analogue mathematical structures. Because almost no-one works in stochastic-analogue terms, there is a dearth of established results and a consequent lack of leverage for people who do work with these ideas.

It's a good Question. I look forward to seeing a more conventional Answer that I hope will be forthcoming from someone else.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.