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, ...
- 24.3k
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(\...
- 2,164
9
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 ...
- 24.3k
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. ...
- 50.9k
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 ...
- 24.3k
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.
- 91
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 ...
- 8,598
7
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 ...
- 4,475
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 ...
- 36.9k
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 ...
- 1,498
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 ...
- 24.3k
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
- 644
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 ...
- 5,273
5
votes
Accepted
Dimension of the Fourier transform for $S_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 ...
- 24.3k
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 ...
- 22.6k
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) ...
- 56
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) ...
- 148
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 ...
- 181
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 ...
- 36.9k
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 ...
- 583
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 ...
- 541
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 ...
- 3,033
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 ...
- 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 ...
- 4,475
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 ...
1
vote
Accepted
How the hardness of hidden subgroup problem in $S_n$ changes as the order of the subgroup grows?
At worst you have to check one element of each repeated prime cycle, https://oeis.org/A186202 Smaller than n! but still large.
- 2,359
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 ...
- 2,359
1
vote
How Much Computing Power would be Required to Fully Simulate a Cubic Meter?
tricky question! there is some diverse crosscutting research into this question, and will attempt to outline it, but will in the end take the position here that the question is contradictory/ ...
- 11k
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible