Questions tagged [physics]
The physics tag has no usage guidance.
68
questions
4
votes
1
answer
167
views
Computation with cellular automata in practice
It is well known that certain cellular automata (CA) are computationally universal, such as Conway's game of life in 2 dimensions or the rule 110 in 1 dimension. As far as I know, they can emulate ...
- 141
1
vote
1
answer
216
views
Computational complexity and general relativity
According to general relativity, the time that a Turing Machine near a massive object spends on computing every step is longer than the time that the Turing Machine far awayfrom a massive object ...
- 101
0
votes
2
answers
376
views
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
Anyone has proved the error rate of quantum computation is bounded by (less than) a constant rather than a function dependent on time and environment by quantum theory? For error rate and error ...
- 1,058
1
vote
0
answers
60
views
Generalization of computability to continuous for loops? [closed]
A computable function, formulated in the sense of mu recursion, can compute a for or do loop over some (possibly infinite) integer range.
I was wondering if a suitable generalization exists that ...
3
votes
0
answers
273
views
Understanding the Physical Church-Turing thesis and its implications
Question:
Most of the applied mathematicians I know have considered Wigner's essay [3] at some point in their lives. Over time my intuition for this empirical observation of the immense progress of ...
- 311
8
votes
1
answer
466
views
Quantum Money where not even the Bank can counterfeit
The Quantum Money system proposed in "Quantum Copy-Protection and Quantum Money" has the following properties:
The bank can produce bank notes in the form of quantum states.
Anyone can verify that ...
- 471
1
vote
2
answers
360
views
Is true randomness and the physical Church-Turing thesis incompatible?
As follow up to Does the physical Church-Turing thesis imply that all physical constants are computable?, I ask if true randomness (as predicted by QM) and the physical Church-Turing thesis are ...
- 471
3
votes
2
answers
437
views
Does the physical Church-Turing thesis imply that all physical constants are computable?
The physical Church Turing thesis is a conjecture that any physically computable algorithm can be computed by a Turing machine.
Let us create a machine that, for example, outputs the digits of the ...
- 471
8
votes
4
answers
1k
views
Stephen Hawking's impact on computer science
In light of Stephen Hawking passing away today, I was wondering whether any of his results have direct impact on cs?
The obvious candidate would be in quantum computing, or rather the construction ...
- 5,531
5
votes
1
answer
364
views
Is it possible to infer on the thermodynamics of two problems if a reduction from $B$ to $A$ exists?
Peter Shor commented on this post:
years of experience in theoretical computer science says that the thermodynamic behavior of two NP complete problems are in general not similar.
What can we say ...
- 463
8
votes
2
answers
1k
views
Isn't it "trivial" to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?
In the late 80's there were several highly cited efforts to use Spin-Glass models to formulate other computational problems such as: Protein Folding and Neural Networks.
Isn't it straight forward to ...
- 463
4
votes
1
answer
345
views
The Maxwell's Demon and Computer Science
What is the best source -in terms of quality- that would explain the argument that uses computations concepts to demonstrate that the Maxwell's Demon does not break the second law of thermodynamics? I ...
- 583
6
votes
2
answers
772
views
Applications of Takens' theorem to TCS?
My apologies if the question is a tad vague—I did try to search the literature for more, but didn't find anything (the similarity between the keywords "Takens" and "taken" on Google may be partly to ...
- 4,451
11
votes
1
answer
492
views
What does a tangible Quantum-Gate look like?
I'v read published books, articles and papers about Quantum-Computing.
I found that all the materials I've seen are, instead of describing quantum gate from basic physics to abstraction, trying hard ...
- 221
2
votes
1
answer
199
views
Complexity of computing generalised determinants. (P - #P transition)
Computing the determinant of a matrix can be done in polynomial time, while computing the permanent is known to be #P-hard. Let $A$ be an $n \times n$ matrix. Define a generalised determinant function ...
- 141
5
votes
1
answer
650
views
Which areas of computer science have lots of overlap with physics?
I'm an undergrad in computer science but I've always loved physics and its ability to constantly amaze and surprise us about our world. I am wondering if there are areas in graduate level computer ...
- 51
2
votes
1
answer
100
views
Why is it impossible to work with polylog length encoding schemes for quantum circuits?
I am going through Quantum Computational Complexity by John Watrous. On page $12$, he said:
The encoding disallows compression: it is not possible to work with
encoding schemes that allow for ...
- 653
1
vote
1
answer
100
views
How the hardness of hidden subgroup problem in $S_n$ changes as the order of the subgroup grows?
In Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In this paper it is showed that no hidden subgroup algorithm can distinguish the trivial ...
- 653
4
votes
2
answers
219
views
Is there any hidden subgroup of a symmetric group which can be efficiently determined?
There have been a number of cases where efficient hidden subgroup algorithms have been found for specific non-Abelian groups with very specific structures. Why haven't we found any efficient quantum ...
- 653
2
votes
0
answers
123
views
Why hidden subgroup problem is easy for very large subgroup?
I am going through QUANTUM MECHANICAL ALGORITHMS FOR THE
NONABELIAN HIDDEN SUBGROUP PROBLEM by Grigni et al. On page 2, it is said that solving the hidden subgroup problem becomes very easy when the ...
- 653
2
votes
0
answers
271
views
Are ill-posed inverse problems in NP?
I'm a physicist who works on inverse problems; I'll explain what these are by means of an example. Consider an object whose refractive index is known; then, the problem of computing scattered ...
- 121
-3
votes
1
answer
144
views
Dimension of the Fourier transform for $S_5$ [closed]
My question:
What is the dimension of the Fourier transform for $S_5$?
My effort:
The dimensions of the seven irreps of $S_5$ are $1,1,4,4,5,5,6$. According to the notes of Andrew Childs, the ...
- 653
5
votes
1
answer
563
views
How Much Computing Power would be Required to Fully Simulate a Cubic Meter?
Imagine you want to simulate a cubic meter down to the particle. By following the Standard Model and other basic physical equations, how much computing power would be required to do this, in say, a ...
- 151
4
votes
0
answers
79
views
Does simulating chiral gauge theories lie within BQP?
In theoretical physics, there is a branch of quantum field theory dealing with chiral gauge theories. It has been conjectured by Feynman [1] and others that all quantum field theories can be simulated ...
- 41
7
votes
3
answers
296
views
Is there a theory of computation that takes failure and decay of the computation substrate into account?
There are obvious differences between a Turing machine and a real computer. Not only is the latter finite in size, it is also prone to failures and it is made from decaying matter. The kind of ...
- 314
9
votes
1
answer
397
views
Is it conceivable at all that the standard model of physics can outperform a quantum computer in any sense?
The Standard Model of physics (the mathematical model which predicts the Higg's boson) is, as far as I understand, our most complete model of the universe. That is to say, it is the best description ...
- 117
8
votes
2
answers
597
views
Suppose $\mathbf{P} = \mathbf{BQP}$. Then what is randomness? Would it even exist at all?
DISCLAIMERI do apologize in advance if this question turns out to be
silly, for some trivial reason that I may be overlooking in this
moment.
Suppose for a moment that $\mathbf{P} = \mathbf{BQP}$ ...
- 6,782
1
vote
0
answers
37
views
Coset state of $3$-node graph isomorphism problem
The hidden subgroup representation of a $3$-node graph isomorphism problem is defined over the symmetric group, $G = S_6$. So, any hidden subgroup algorithm that wishes to solve the problem should ...
- 653
2
votes
1
answer
971
views
Complexity: simulated annealing vs. quantum annealing
How do I compare the performance of simulated annealing against the performance of quantum annealing algorithms?
In Convergence theorems for quantum annealing by Morita and Nishimori, it has been ...
- 653
11
votes
1
answer
664
views
Quantum algorithms for QED computations related to the fine structure constants
My question is about quantum algorithms for QED (quantum electrodynamics) computations related to the fine structure constants. Such computations (as explained to me) amounts to computing Taylor-like ...
- 6,013
-1
votes
4
answers
506
views
How could God authenticate in one message? [closed]
Thought experiment:
Which data could convince experts, beyond reasonable doubts, about their origin outside our universe? From which margin should an expert consider such claim seriously?
For example,...
- 155
2
votes
0
answers
134
views
Calculating the ground state of an Ising model with $\sigma_i = (0,1)$ spin state assignments (do Barahona & Istrail's NP-hardness results hold?)
In a typical Ising model, one has possible spin assignments of $\sigma_i = \pm 1$. However, one can also imagine a $q = 2$ Potts model generalization with spin assignments $\sigma_i = (0,1)$. Is ...
-1
votes
1
answer
97
views
The Arrow of Time in a Non-Physical Realm [closed]
Could there be a logically consistent theory supporting the transmission of non-physical information to a point in time previous to the time it was sent using a computer network (quantum theory, etc)? ...
- 11
0
votes
1
answer
117
views
References to learn more about graph laplacian.
I have vaguely heard of this connection between random matrix theory and graphs (the spectral gap of their laplacians) on compact Riemann surfaces.
Can someone give a pedagogic reference which helps ...
- 271
2
votes
0
answers
56
views
How the errors of the measured quantities of an adiabatic Hamiltonian are inversely proportional to the square root of the number of measurements?
I am going through the paper, Solving the graph-isomorphism problem with a quantum annealer, by Hen et. al. In the last line of the second paragraph of the second column of page 2, it says,
Since ...
- 653
4
votes
2
answers
369
views
Simulation of every physical quantum system on quantum computer
Let me quote from the section 9.3 of Classical and Quantum Computation by Kitaev, Shen and Vyalyi.
With high confidence, we may claim that every physical quantum system
can be efficiently ...
- 653
19
votes
1
answer
305
views
Is there a geometrical picture for adiabatic quantum computation?
In adiabatic quantum computation (AQC), one encodes the solution to an optimization problem in the ground state of a [problem] Hamiltonian $H_p$. To get to this ground state, you start in an easily ...
- 431
0
votes
1
answer
102
views
Confusion with the proof of constraints for a particular adiabatic quantum evolution
[This might be related to one of my previous unanswered questions.]
This proof belongs to the paper, How to Make the Quantum Adiabatic Algorithm Fail by Edward Farhi, Jeffrey Goldstone, Sam Gutmann ...
- 653
3
votes
1
answer
104
views
Questions about Farhi's pre-Adiabatic paper
I have been going through Eddie Farhi's 6-pages long pre-Adiabatic paper, An Analog Analogue of a Digital Quantum Computation.
I guess I understand most of the math and physics but I am struggling ...
- 653
6
votes
0
answers
182
views
Local Hamiltonian and combinatorial search problems
I was going through the PhD thesis of Daniel Nagaj. At the beginning of chapter two he indicated a relation between the local Hamiltonian perspective of adiabatic quantum computation and combination ...
- 653
7
votes
0
answers
281
views
Implication of Bell test loopholes on Vazirani-Vidick random sequence generation scheme
I am trying to imagine what would be the implications of the loopholes on Bell test on the random sequence generation scheme proposed by Vazirani and Vidick (VV protocol) in the paper titled '...
- 653
7
votes
2
answers
960
views
Application of methods from dynamical system to the study of k-SAT and similar problems
I am looking for literature (survey and non-survey papers) about
transforming the k-SAT problem (or similar problems) into
a system of Ordinary Differential Equations (ODEs) and
study the solution of ...
- 73
9
votes
1
answer
6k
views
Quantum annealing vs adiabatic quantum computation
I had this impression that quantum annealing is an optimization technique which may or may not produce exact solutions. On the other hand adiabatic quantum computation always gives exact solutions ...
- 653
22
votes
1
answer
462
views
Exact planar electrical flow
Consider an electrical network modeled as a planar graph G, where each edge represents a 1Ω resistor. How quickly can we compute the exact effective resistance between two vertices in G? ...
- 23.1k
32
votes
7
answers
10k
views
Should we consider $\mathsf{P} \neq \mathsf{NP}$ a law of nature?
Many experts believe that the $\mathsf{P} \neq \mathsf{NP}$ conjecture is true and use it in their results. My concern is that the complexity strongly depends on the $\mathsf{P} \neq \mathsf{NP}$ ...
- 4,828
1
vote
1
answer
311
views
What's the nature of hypercomputing and relativity?
Somewhere I read something like "a hypercomputer rotating around a rotating black hole" would have some esoteric properties e.g. would produce other answers than other hypercomputers and other ...
7
votes
3
answers
4k
views
Are Shannon entropy and Boltzmann entropy mutually convertible?
Are Shannon entropy and Boltzmann entropy mutually convertible, much like mass and energy according to Einstein's formula?
- 207
18
votes
1
answer
2k
views
Feasibility of Gödel machines
Recently I stumbled upon quite an interesting theoretical construct. A so called Gödel machine
It's a general problem solver which is capable of self-optimization. It's suitable for reactive ...
- 333
11
votes
3
answers
386
views
Reductions of hard problems to physical models
I am looking for examples of hard problems (in NP or harder) from computer science which can be reduced to models of physical processes.
For example, max-2-sat can be reduced to energy minimization ...
- 113
7
votes
3
answers
2k
views
Physical realization of nonlinear operators for quantum computers.
I have read in a paper where nonlinear operators for quantum computers implies the solving of problems in #P time. See http://arxiv.org/pdf/quant-ph/9801041 .
What would be the simplest realization of ...
- 1,641