17
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, ...
- 23.9k
16
votes
Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?
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 ...
- 7,185
12
votes
Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?
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 ...
- 5,973
10
votes
Is it conceivable at all that the standard model of physics can outperform a quantum computer in any sense?
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 ...
- 23.9k
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 ...
- 23.9k
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.5k
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,049
9
votes
Accepted
Is there a theory of computation that takes failure and decay of the computation substrate into account?
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 ...
- 10.6k
8
votes
Accepted
Quantum annealing vs adiabatic quantum computation
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-...
- 540
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
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 ...
- 23.9k
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,455
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,223
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.3k
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,478
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 ...
- 23.9k
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,038
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
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 ...
- 23.9k
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.4k
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
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
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.3k
3
votes
Is there a theory of computation that takes failure and decay of the computation substrate into account?
Rabie introduced the model of "Rusted Turing Machines" in his thesis: The Power of Weaknesses:What can be computed with Populations, Protocols and Machines (Chapter 7).
The idea is that there is a ...
- 1,645
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
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 ...
- 563
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 ...
- 540
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,013
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,455
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 ...
Only top scored, non community-wiki answers of a minimum length are eligible