FFT describes everything with sinusoids by default. For QFT, it's wave functions. Wavelets are more like NN neurons that match (scale-invariant?) quantized sections of waveforms.
A classical universal function approximator is probably not sufficient to approximate quantum systems
(unless there is IDK a geometric breakthrough in classical-quantum correspondence similar to the Amplituhedron).
IIUC Church-Turing and Church-Turing-Deutsch say that Turing complete is enough for classical computing, and that a qubit computer can simulate the same quantum logic circuits as any qudit or qutrit computer; but is it ever shown that Quantum Logic is indeed the correct and sufficient logic for propositional calculus and also for all physical systems?
> - The rotation operators Rx(θ), Ry(θ), Rz(θ), the phase shift gate P(φ)[c] and CNOT are commonly used to form a universal quantum gate set.
> - The Clifford set {CNOT, H, S} + T gate. The Clifford set alone is not a universal quantum gate set, as it can be efficiently simulated classically according to the Gottesman–Knill theorem.
> - The Toffoli gate + Hadamard gate.[17] The Toffoli gate alone forms a set of universal gates for reversible boolean algebraic logic circuits which encompasses all classical computation.
[...]
> - The parametrized three-qubit Deutsch gate D(θ)
> A universal logic gate for reversible classical computing, the Toffoli gate, is reducible to the Deutsch gate, D(π/2), thus showing that all reversible classical logic operations can be performed on a universal quantum computer.
Turing machines can also be used as universal function approximators. But I'm not sure it makes sense to put them in the same category as the other two.
I would love to put them in the same category as the other two. In fact I’ve spent quite a lot if time thinking about it / experimenting. Wouldn’t it be great if we could somehow train on data and get a small Turing machine instead of a huge neural network?
Universal approximation theorem: https://en.wikipedia.org/wiki/Universal_approximation_theore...
NAND is a universal logic gate; from which all classical functions can be approximated.
CCNOT and Hadamard are universal logic gates with which all (?) quantum functions/transforms can be approximated.
Cubic splines are universal function approximators. As is piecewise linear interpolation. The universal function approximator thing is way overblown.
FFT describes everything with sinusoids by default. For QFT, it's wave functions. Wavelets are more like NN neurons that match (scale-invariant?) quantized sections of waveforms.
Fluids are decomposed into things with curl.
A classical universal function approximator is probably not sufficient to approximate quantum systems [...] https://news.ycombinator.com/item?id=37379123
> CCNOT and Hadamard are universal logic gates with which all (?) quantum functions/transforms can be approximated.
CNOT, H, S, and T are universal for approximating any quantum operation.
A classical universal function approximator is probably not sufficient to approximate quantum systems (unless there is IDK a geometric breakthrough in classical-quantum correspondence similar to the Amplituhedron).
IIUC Church-Turing and Church-Turing-Deutsch say that Turing complete is enough for classical computing, and that a qubit computer can simulate the same quantum logic circuits as any qudit or qutrit computer; but is it ever shown that Quantum Logic is indeed the correct and sufficient logic for propositional calculus and also for all physical systems?
From "Quantum logic gate > Universal quantum gates": https://en.wikipedia.org/wiki/Quantum_logic_gate#Universal_q... :
> Some universal quantum gate sets include:
> - The rotation operators Rx(θ), Ry(θ), Rz(θ), the phase shift gate P(φ)[c] and CNOT are commonly used to form a universal quantum gate set.
> - The Clifford set {CNOT, H, S} + T gate. The Clifford set alone is not a universal quantum gate set, as it can be efficiently simulated classically according to the Gottesman–Knill theorem.
> - The Toffoli gate + Hadamard gate.[17] The Toffoli gate alone forms a set of universal gates for reversible boolean algebraic logic circuits which encompasses all classical computation.
[...]
> - The parametrized three-qubit Deutsch gate D(θ)
> A universal logic gate for reversible classical computing, the Toffoli gate, is reducible to the Deutsch gate, D(π/2), thus showing that all reversible classical logic operations can be performed on a universal quantum computer.
CCNOT: https://en.wikipedia.org/wiki/Toffoli_gate https://en.wikipedia.org/wiki/Quantum_logic_gate#Toffoli_(CC...
CNOT: https://en.wikipedia.org/wiki/Controlled_NOT_gate
H: https://en.wikipedia.org/wiki/Quantum_logic_gate#Hadamard_ga...
S: https://en.wikipedia.org/wiki/Quantum_logic_gate#Phase_shift...
T: https://en.wikipedia.org/wiki/Quantum_logic_gate#Phase_shift...
Implicit to a quantum approximator would be at least Quantum statistical mechanics and maybe also Quantum logic:
Quantum statistical mechanics: https://en.wikipedia.org/wiki/Quantum_statistical_mechanics
Quantum logic: https://en.wikipedia.org/wiki/Quantum_logic
All quantum functions can be approximated with a three layer perceptron, or by arbitary boolean logic.
Quantum computers can only compute - just like any other computer.
Turing machines can also be used as universal function approximators. But I'm not sure it makes sense to put them in the same category as the other two.
I would love to put them in the same category as the other two. In fact I’ve spent quite a lot if time thinking about it / experimenting. Wouldn’t it be great if we could somehow train on data and get a small Turing machine instead of a huge neural network?
I would expect it to result in a large and slow Turing machine instead of a small neural network.
4 replies →
Depends which valley it chooses to die on
Yup - and that's the big question for ML... "which valley will this algorithm die on" so far I haven't seen an answer.