18 votes
Accepted

What does a tangible Quantum-Gate look like?

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, ...
Peter Shor 's user avatar
10 votes

Does the physical Church-Turing thesis imply that all physical constants are computable?

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 ...
Peter Shor 's user avatar
9 votes
Accepted

Complexity of computing generalised determinants. (P - #P transition)

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(\...
holf's user avatar
  • 2,174
9 votes

Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?

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. ...
David Eppstein's user avatar
8 votes

Stephen Hawking's impact on computer science

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.
Anonymous's user avatar
8 votes
Accepted

Does the physical Church-Turing thesis imply that all physical constants are computable?

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 ...
Bjørn Kjos-Hanssen's user avatar
8 votes
Accepted

Quantum Money where not even the Bank can counterfeit

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 ...
Peter Shor 's user avatar
7 votes

Richard Feynman says that all quantum procedures are able to be simulated by quantum computation

Since we don't know the ultimate physical laws of the universe, and we would need to know them (or at least know much more about them than we do now) to prove Feynman's conjecture, his conjecture is ...
Peter Shor 's user avatar
7 votes

Stephen Hawking's impact on computer science

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 ...
Denis's user avatar
  • 8,843
6 votes

Is it possible to infer on the thermodynamics of two problems if a reduction from $B$ to $A$ exists?

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 ...
Joshua Grochow's user avatar
6 votes
Accepted

Why is it impossible to work with polylog length encoding schemes for quantum circuits?

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 ...
Craig Gidney's user avatar
  • 1,518
5 votes

Is it proved that error rate of quantum computation is bounded by constant rather than a function dependent on time and environment by quantum theory

As far as I know, nobody has come up with a convincing physics reason that fault-tolerant quantum computing is fundamentally impossible. However, it is a formidable engineering task, which is why we ...
Peter Shor 's user avatar
5 votes

Which areas of computer science have lots of overlap with physics?

[The following is more an extended comment with pointers than a real answer.] If you were in France, a good answer would be combinatorial physics. I say "if you were in France" because, for reasons ...
Damiano Mazza's user avatar
5 votes

Stephen Hawking's impact on computer science

Not a direct answer but something : He is mentioned 19 times in these lecture notes of Scott Aaronson, https://www.scottaaronson.com/barbados-2016.pdf That says something, I guess? :D
Student's user avatar
  • 654
4 votes

Stephen Hawking's impact on computer science

He gave a little indirect concrete (not theoretical) contribution to assistive technologies: Stephen Hawking's speech tech released by Intel: "... Software that helps Prof Stephen Hawking to speak ...
Marzio De Biasi's user avatar
4 votes
Accepted

The Maxwell's Demon and Computer Science

A good place to start looking at these ideas is this paper, though it talks about the (related) idea of information and thermodynamics. It relates fundamental computational tasks (eg. editing a bit) ...
Abhishek Shetty's user avatar
4 votes
Accepted

Applications of Takens' theorem to TCS?

Takens himself did some CS work although not TCS work. He did some attractor reconstruction stuff with neural networks, for example (https://clgiles.ist.psu.edu/papers/NC-2000-learning-chaos-nn.pdf) ...
Howon's user avatar
  • 56
3 votes

Computation with cellular automata in practice

To be more precise, I would want that the runtime scaling for the universal CA of each task is the same as for the best CA specifically designed for that task. Game of life is intrinsically universal ...
user148606's user avatar
3 votes
Accepted

Is there any hidden subgroup of a symmetric group which can be efficiently determined?

From what I understand, it is partially because we don't have any techniques currently that take advantage of structure of the hidden subgroup itself. Weak Fourier sampling solves the problem whenever ...
Joshua Grochow's user avatar
2 votes

Physics results in TCS?

I know some examples in machine learning. It is very common for thermodynamic ideas to be used in this area: Boltzmann machine, Hopfield network, Wake-sleep algorithm. Markov Chain were initially used ...
Raphael Augusto's user avatar
2 votes
Accepted

Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?

It was only recently (2016) that it was proved mathematically that all of classical spin physics can be reproduced by the 2D Ising Model with linear terms (what physicists call "fields") with at most ...
user1271772's user avatar
2 votes

Is true randomness and the physical Church-Turing thesis incompatible?

The Church-Turing thesis is about (partial) functions $\mathbb{N} \to \mathbb{N}$ (or $\Sigma^* \to \Sigma^*$ for a finite alphabet $\Sigma$). How do you define a definite value based on some random ...
Thomas Klimpel's user avatar
1 vote

Computational complexity and general relativity

The speed doesn't increase without bound as you move away from massive objects. It only increases to a maximum of about $1+GM/rc^2$ times faster. If $M$ and $r$ are the mass and radius of Earth, this ...
benrg's user avatar
  • 186
1 vote

Is true randomness and the physical Church-Turing thesis incompatible?

In a way, if we imagine time continuing indefinitely then with probability 1, random numbers, obtained from I guess the collapse of the wave function in quantum mechanics, will form a non-computable ...
Bjørn Kjos-Hanssen's user avatar
1 vote

Applications of Takens' theorem to TCS?

Theoretically, Takens's theorem implies that a deterministic system attractor of finite dimension $D$ can be reconstructed by a finite number of time delays $k$ if $$ k \geq 2D + 1. $$ This implies ...
Kalinda Vathupola's user avatar
1 vote

Is there any hidden subgroup of a symmetric group which can be efficiently determined?

Exact classical bounds are known, https://oeis.org/A186202 , you only have to sample certain prime cycles as they form a min dominating set on $S_n$ under a detection relation. Smaller than $n!$ but ...
Chad Brewbaker's user avatar
1 vote
Accepted

Complexity: simulated annealing vs. quantum annealing

In Rough Large Deviation Estimates for Simulated Annealing: Application to Exponential Schedules a theoretical justification for the exponential cooling schedule was given. The results there basically ...
mithrawnuruodo's user avatar

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