Hot answers tagged

17

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, quantum gates may be just conceptual. Consider an ion trap. The ions represent qubits by using one electronic state as a $|0\rangle$ and another as a $|1 \rangle$...


16

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 this deterministic function (at the cost of sometimes being wrong), or does not. This is the key point: P=BQP says nothing about outputting random strings in ...


13

The general belief seems to be that the expansion in $\alpha$ is an asymptotic series but not a convergent series. The handwaving estimate is that in $\sum_k c_k \alpha^k$, the scaling for the coefficients is roughly $c_k \sim k!$. So, since $\alpha \simeq 1/137$ the terms will start to get bigger rather than smaller for $k$ larger than around 137. (I assume ...


11

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 is not clear that referring just to decision problems suffices to do justice to the power of quantum computing. If we let QSAMPLING describes the probability ...


10

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 power beyond BQP. Simulating quantum field theories with a quantum computer is not an easy task, but a start has been made by this paper by Jordan, Lee, and ...


9

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(\theta)Perm(A)+i\sin(\theta)Det(A)$. Thus, if $\cos(\theta) \neq 0$, we have $Perm(A) = (Det_\theta(A)-i\sin(\theta)Det(A))/\cos(\theta)$, meaning that $Det_\...


9

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 are asking about. I don't have time to give a complete overview, but here are some pointers that may be of interest. Distributed systems. This is probably by far ...


9

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. Because of this these problems can often be NP-hard but not (or not obviously) NP-complete. For instance, we do not know whether the Euclidean TSP (for integer ...


9

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 value of the fine-structure constant, it cannot predict the outcome of an arbitrary experiment. I don't believe (b) is the case. Generally, the way that ...


8

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.


8

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 Knots, Mark Zhandry's paper Quantum Lightning Never Strikes the Same State Twice, Daniel Kane's paper Quantum Money from Modular Forms. In order to make ...


7

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-Lipton model (a model for computing using DNA) Turing machine model (a model where computations are done with symbols on a tape) One can devise algorithms using ...


7

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 in general waves carrying information are swallowed by a black hole, the information they carry seems to be destroyed. This violates principles in quantum ...


7

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 thesis. But in practice, $\alpha$ is based on some measured quantities, we have no Theory of Everything (TOE) for physics, and it is not clear that $\alpha$ is a ...


6

We will never be able to prove this statement, because we can never be able to know for sure whether we have the exact laws of physics, or just a very good approximation to them. Even if we had a satisfactory theory of everything which we could use to make good predictions about every experimentally measurable physical system, there would be no way to tell ...


6

Basically everything that is known about the Quantum PCP conjecture has been collected in this survey by Dorit Aharonov, Itai Arad, and Thomas Vidick: The Quantum PCP Conjecture See also Thomas' blog post on the topic.


6

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 context the author is in the middle of explaining the complexity class BQP (bounded-probability quantum polynomial-time). I think they're just making sure that you ...


6

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 example, if we consider not just the complexity of languages, but also the complexity of functions, every language is equivalent (under pretty simple reductions) to ...


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 of group elements. The number of basis states after the Fourier transform is 120, in this case broken up according to the identity $$ 120=1^2+1^2+4^2+4^2+5^2+...


5

[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 that escape me but that must be mostly historical, in France combinatorics is considered part of theoretical computer science :-) In the rest of the world, ...


5

Everything interesting happens in this paper happens within the 2D subspace generated by the two vectors $|s\rangle$ and $|w\rangle$. The vector $|r\rangle$ is a vector from this subspace orthogonal to $|w\rangle$, giving us the basis $|w\rangle, |r\rangle$, where the analysis will be very simple (using 2x2 matrices). The norm in the second question is ...


5

First of all is the known weaker result $NL\neq PSPACE$ or the stronger conjecture $NP\neq coNP$ possible laws of nature? Then we can ask questions about if $P\neq NP$ is a law of nature.


5

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


4

For the consequences of such transmission to theoretical computer science (the only aspect of your question that is on-topic here) see Aaronson and Watrous's "Closed Timelike Curves Make Quantum and Classical Computing Equivalent".


4

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) and it does use his embedding theorem to suggest nonlinear autoregressive (time delay) neural nets, and look towards actual recurrent networks. Overall, ...


4

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) to fundamental thermodynamic tasks (eg. energy extraction). Following the links within the paper should give reasonable access to literature on the subject. Also,...


4

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 via a computer has been published online by Intel, the company that created it. ..." There is a short description also on his site.


3

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 the hidden subgroup is normal (but this is not a property of the subgroup itself - analogous to being a direct product etc - but rather how the subgroup sits ...


3

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 restriction on the number of time the TM can change its internal state because of decay. Rabie introduced the class $Piv(f(n))$, the class of Turing Machines that ...


3

The norms are the usual norms of a ket vector, i.e. $|||a\rangle||^2 = \langle a|a\rangle$. What did we do on the bottom of page 3? It is really running the argument from the An Analog Analogue paper backwards. Imagine we start from the state $|g_x\rangle$ (a particular ground state of the final Hamiltonian $H_{P}$, related to $|x\rangle$), and evolve ...


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