Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [physics]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-3 votes
1 answer
229 views

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

Richard Feynman says that all quantum procedures are able to be simulated by quantum computation,but his argument is not rigid, it seems to be a conjecture. Is there any physics/math argument ...
XL _At_Here_There's user avatar
4 votes
1 answer
177 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 ...
Andi Bauer's user avatar
1 vote
1 answer
259 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 ...
WangAtChicago's user avatar
0 votes
2 answers
402 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 ...
XL _At_Here_There's user avatar
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 ...
Abhimanyu Pallavi Sudhir's user avatar
3 votes
0 answers
285 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 ...
Aidan Rocke's user avatar
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 ...
Christopher King's user avatar
1 vote
2 answers
366 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 ...
Christopher King's user avatar
4 votes
2 answers
449 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 ...
Christopher King's user avatar
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 ...
Shaull's user avatar
  • 5,646
5 votes
1 answer
367 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 ...
0x90's user avatar
  • 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 ...
0x90's user avatar
  • 463
4 votes
1 answer
348 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 ...
Raphael Augusto's user avatar
6 votes
2 answers
780 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 ...
Clement C.'s user avatar
  • 4,471
11 votes
1 answer
497 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 ...
Chiron's user avatar
  • 221
2 votes
1 answer
200 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 ...
biryani's user avatar
  • 141
5 votes
1 answer
658 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 ...
aspCSmjr's user avatar
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 ...
Omar Shehab's user avatar
1 vote
1 answer
101 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 ...
Omar Shehab's user avatar
4 votes
2 answers
222 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 ...
Omar Shehab's user avatar
2 votes
0 answers
131 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 ...
Omar Shehab's user avatar
2 votes
0 answers
282 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 ...
xadu's user avatar
  • 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 ...
Omar Shehab's user avatar
5 votes
1 answer
578 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 ...
APCoding's user avatar
  • 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 ...
CS physicist's user avatar
7 votes
3 answers
306 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 ...
Lenar Hoyt's user avatar
9 votes
1 answer
409 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 ...
Chris Blake's user avatar
8 votes
2 answers
608 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}$ ...
Giorgio Camerani's user avatar
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 ...
Omar Shehab's user avatar
2 votes
1 answer
977 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 ...
Omar Shehab's user avatar
11 votes
1 answer
674 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 ...
Gil Kalai's user avatar
  • 6,053
-1 votes
4 answers
509 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,...
Incnis Mrsi's user avatar
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 ...
QIBincomplete's user avatar
-1 votes
1 answer
99 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)? ...
Manborg's user avatar
  • 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 ...
user6818's user avatar
  • 281
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 ...
Omar Shehab's user avatar
4 votes
2 answers
375 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 ...
Omar Shehab's user avatar
19 votes
1 answer
309 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 ...
hadsed's user avatar
  • 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 ...
Omar Shehab's user avatar
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 ...
Omar Shehab's user avatar
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 ...
Omar Shehab's user avatar
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 '...
Omar Shehab's user avatar
7 votes
2 answers
964 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 ...
nonlinearism's user avatar
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 ...
Omar Shehab's user avatar
22 votes
1 answer
471 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? ...
Jeffε's user avatar
  • 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}$ ...
vb le's user avatar
  • 4,828
1 vote
1 answer
316 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 ...
Niklas Rosencrantz's user avatar
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?
Mok-Kong Shen's user avatar
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 ...
Dmitry Vyal's user avatar
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 ...
mdenil's user avatar
  • 113