@article{vergis1986cac,
title={The Complexity of Analog Computation},
author={Vergis, A. and Steiglitz, K. and Dickinson, B.},
journal={Mathematics \& Computers in Simulation},
volume={28},
pages={91--113},
year={1986},
comment = {Claims a digital computer can efficiently simulate an
analog one, and an analog one can't solve NP
problems if a digital one can't.}
}
@article{turan1994cbf,
title={{On the computation of Boolean functions by analog circuits ofbounded fan-in}},
author={Turan, G. and Vatan, F.},
journal={Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on},
pages={553--564},
year={1994},
comment = {Haven't read yet...}
}
@article{maass1998ean,
title={{On the effect of analog noise in discrete-time analog computations}},
author={Maass, W. and Orponen, P.},
journal={Neural Computation},
volume={10},
number={5},
pages={1071--1095},
year={1998},
publisher={MIT Press Cambridge, MA, USA}
}
The Turan paper requires an IEEE Digital Library subscription to get, the others are available free on the web if you look.
Hi SuperPerro1,
ReplyDeleteThanks for the compliment :-).
I wish I had a good reference on circuit complexity, but I don't offhand. One place to start is The Source -- Knuth's The Art of Computer Programming. In there you will find things such as a discussion of how the performance can actually depend on the architecture of a computer (an obvious point which is often overlooked) -- a Turing Machine behaves very differently from one with random-access memory. Hope that helps.
Hi Leucipo,
ReplyDeleteThere is a lot of discussion about the relationship between quantum and analog computation, of course, and it sometimes gets heated; I think people are usually coming from a particular set of assumptions that are not always well articulated.
QC is much more than just analog computation, with its computational power coming from the superposition and entanglement of quantum variables. But, in my opinion, it's difficult to see how someone can claim that QC is not analog computation, when quantum algorithms are defined in terms of continuous rotation angles. Of course, as long as we're talking about qubits, the end result of a measurement is always a binary value, so it's not exactly analog; then, of course, there are the continuous quantum variables (qunats), which are a whole different ball of wax.