Comment by westurner
3 years ago
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.