Hot answers tagged

57

Strassen's statement needs to be put into context. This was an address to an audience of mathematicians in 1986, a time when many mathematicians did not have a high opinion of theoretical computer science. The complete statement is For some of you it may seem that the theories discussed here rest on weak foundations. They do not. The evidence in favor of ...


21

Can such machines be built in practice? Yes. By "machine", Schmidhuber just means "computer program". Are they at least feasible in our Universe? Not in their current form -- the algorithms are too inefficient. From a ten thousand meter perspective, Jürgen Schmidhuber (and former students, like Marcus Hutter) have been investigating the idea of ...


20

I can see three related ways to understand the question: 1) Can we we regard $NP \ne P$ as a fundamental principle of computational complexity theory, even before we can prove it? 2) Does the $NP \ne P$ principle extends beyond its narrow mathematical meaning? 3) Does the $NP \ne P$ principle can be regarded as a physical law. I think that there are ...


17

You seem to have the idea that a quantum gate is a physical thing rather than just a conceptual thing. It doesn't necessarily work that way. While CMOS gates are usually actual physical devices, quantum gates may be just conceptual. Consider an ion trap. The ions represent qubits by using one electronic state as a $|0\rangle$ and another as a $|1 \rangle$...


16

In practice the only difference is that Boltzmann entropy deals with a thermodynamical constant $K_B$: $ H = -K_B\sum_{i=1}^{N} P_i log_e\ P_i $ i assume you already know that if $K_B=1$ you have Shannon entropy in a different base. However the conceptual backgrounds are important; probability of events (Shannon) and probability of a particle being in one ...


14

P and BQP are decision-problem classes, i.e. the correct output is always a deterministic functions of the inputs. The only question is whether randomness helps "along the way" to speed up computing this deterministic function (at the cost of sometimes being wrong), or does not. This is the key point: P=BQP says nothing about outputting random strings in ...


14

Using nested dissections you can even solve a linear system (based on a planar graph) in $O(\sqrt{n^\omega})$. This was for example noted in a paper I have with Günter Rote and Ares Ribó and in this paper by Alon and Yuster. The former paper also contains an approach how to compute the pairwise resistances between vertices on a a common face in $O(\sqrt{n^...


13

As has already been answered, Shannon entropy and Boltzman entropy are the same thing, although they are measured in different units. You also asked whether there is a practical link. It may not be practical yet, but the idea of algorithmic cooling uses the link between these two concepts, and has indeed been experimentally demonstrated.


12

I'm not sure I understand. A physical law (of the kind you indicate) is a mathematical expression of a model (in that example, relativity) that claims to capture reality. A physical law can be proved wrong if the underlying mathematics is incorrect, but it can also be wrong if the underlying model changes (for example, newtonian mechanics). P vs NP is a ...


12

The general belief seems to be that the expansion in $\alpha$ is an asymptotic series but not a convergent series. The handwaving estimate is that in $\sum_k c_k \alpha^k$, the scaling for the coefficients is roughly $c_k \sim k!$. So, since $\alpha \simeq 1/137$ the terms will start to get bigger rather than smaller for $k$ larger than around 137. (I assume ...


10

The questions touches on some very interesting issues regarding quantum computation (and randomness). BQP is the class of decision problems that can be solved efficiently (in polynomial time) but it is not clear that referring just to decision problems suffices to do justice to the power of quantum computing. If we let QSAMPLING describes the probability ...


10

If quantum computers can simulate in polynomial time the Standard Model, which is a quite complicated quantum field theory, then probably the Standard Model does not provide any extra computational power beyond BQP. Simulating quantum field theories with a quantum computer is not an easy task, but a start has been made by this paper by Jordan, Lee, and ...


9

I'm not 100% sure what the question is about, but the title seems to ask about computation that allows failure. There is a lot of work on noisy (erroneous) computation in the sense that I think you are asking about. I don't have time to give a complete overview, but here are some pointers that may be of interest. Distributed systems. This is probably by far ...


9

I extend my comment in an answer. By rewriting $e^{i \cdot sgn(\mu)\theta} = \cos(sgn(\mu)\theta)+i\sin(sgn(\mu)\theta) = \cos(\theta)+i \cdot sgn(\mu)\sin(\theta)$ we have: $Det_\theta(A) = \cos(\theta)Perm(A)+i\sin(\theta)Det(A)$. Thus, if $\cos(\theta) \neq 0$, we have $Perm(A) = (Det_\theta(A)-i\sin(\theta)Det(A))/\cos(\theta)$, meaning that $Det_\...


9

Classical physical problems often involve real-number positions or parameter values rather than values from a discrete set (such as the integers) which would be more typical of NP-complete problems. Because of this these problems can often be NP-hard but not (or not obviously) NP-complete. For instance, we do not know whether the Euclidean TSP (for integer ...


9

You appear to be positing a universe where (a) the fine-structure constant has an exact value and (b) we can measure as many digits of it as we want. Thus, if a Turing machine cannot compute the exact value of the fine-structure constant, it cannot predict the outcome of an arbitrary experiment. I don't believe (b) is the case. Generally, the way that ...


8

He didn't have any major impact on computer science. His writing in computer science are limited to popsci and more recently raising public concerns about AI.


8

There are proposals for quantum money where it appears that not even the bank can produce two copies of a quantum money state with the same serial number. See Farhi et al's paper Quantum Money from Knots, Mark Zhandry's paper Quantum Lightning Never Strikes the Same State Twice, Daniel Kane's paper Quantum Money from Modular Forms. In order to make ...


7

To answer your original question: Yes at least Scott Aaronson believes that $P \ne NP$ is a law of nature. He proposed the following formulation "The NP Hardness Assumption : There is no physical means to solve NP complete problems in polynomial time". He gave a nice talk at the University of Waterloo titled Computational Intractability As A Law of ...


7

Adiabatic quantum computing (AQC) is a computational model (as Peter said in the comments). Compare AQC with other models of computation such as: circuit-based quantum computing (CBQC) Adleman-Lipton model (a model for computing using DNA) Turing machine model (a model where computations are done with symbols on a tape) One can devise algorithms using ...


7

The Black Hole Information Paradox seems relevant to me, as it concerns information theory, which can be seen as close to computer science. To sum up, the paradox in question is that when objects or in general waves carrying information are swallowed by a black hole, the information they carry seems to be destroyed. This violates principles in quantum ...


7

Yes, if you somehow had a scheme that allows to compute/measure more and more digits of the fine-structure constant $\alpha$ then $\alpha$ should be Turing computable according to the Church-Turing thesis. But in practice, $\alpha$ is based on some measured quantities, we have no Theory of Everything (TOE) for physics, and it is not clear that $\alpha$ is a ...


6

We will never be able to prove this statement, because we can never be able to know for sure whether we have the exact laws of physics, or just a very good approximation to them. Even if we had a satisfactory theory of everything which we could use to make good predictions about every experimentally measurable physical system, there would be no way to tell ...


6

Basically everything that is known about the Quantum PCP conjecture has been collected in this survey by Dorit Aharonov, Itai Arad, and Thomas Vidick: The Quantum PCP Conjecture See also Thomas' blog post on the topic.


6

There are actually sort-of-researchy things one can say about rotating black holes. Namely it is known that sufficiently quick rotation produces time-like simple closed curves, leading to interesting questions about how to model time-travel paradoxes in complexity theory; see Aaronson and Watrous, "Closed Timelike Curves Make Quantum and Classical Computing ...


6

Clearly you can work with abstract compressed representations of circuits. You can reason about them and manipulate them and turn them into concrete lists of gates. We do it all the time. But in context the author is in the middle of explaining the complexity class BQP (bounded-probability quantum polynomial-time). I think they're just making sure that you ...


6

With thermodynamics you have to be careful with the kind of reductions you allow, or (as Peter Shor pointed out) there can be essentially no thermodynamic relationship implied by a reduction. For example, if we consider not just the complexity of languages, but also the complexity of functions, every language is equivalent (under pretty simple reductions) to ...


5

First of all is the known weaker result $NL\neq PSPACE$ or the stronger conjecture $NP\neq coNP$ possible laws of nature? Then we can ask questions about if $P\neq NP$ is a law of nature.


5

Everything interesting happens in this paper happens within the 2D subspace generated by the two vectors $|s\rangle$ and $|w\rangle$. The vector $|r\rangle$ is a vector from this subspace orthogonal to $|w\rangle$, giving us the basis $|w\rangle, |r\rangle$, where the analysis will be very simple (using 2x2 matrices). The norm in the second question is ...


5

A quantum Fourier transform is a unitary operation, so the number of basis states of the input and output must be the same. The number of basis states before the Fourier transform is 120, the number of group elements. The number of basis states after the Fourier transform is 120, in this case broken up according to the identity $$ 120=1^2+1^2+4^2+4^2+5^2+...


Only top voted, non community-wiki answers of a minimum length are eligible