# Tag Info

72

there exist problems that are hard to solve, but for which it is easy to verify the validity of a given solution: the so called NP problems. This statement is wrong. There are many NP problems which are easy to solve. "NP" simply means "easy to verify". It does not mean hard to solve. What you are probably thinking of is NP-complete problems which is a ...

39

While it is true that the computation of a quantum Turing machine is vastly different from that of a classical one, nevertheless quantum Turing machines can be simulated on a classical Turing machine, albeit with exponential slowdown. In particular, everything that can be computed on a quantum Turing machine can also be computed on a classical Turing machine....

36

A quantum computer by itself isn't faster. Instead, it has a different model of computation. In this model, there are algorithms for certain (not all!) problems, which are asymptotically faster than the fastest possible (or fastest known, for some problems) classical algorithms. I recommend reading The Limits of Quantum by Scott Aaronson: it's a short ...

36

No, there will be absolutely no implication, for several reasons: The P vs. NP problem is about classical computation rather than quantum computation. Even if quantum computers could solve NP-hard problems in polynomial time (which we don't expect them to be able to do), it could still be the case that classical computers cannot solve them in polynomial ...

35

You're mixing up computability theory (also known as recursion theory) and complexity theory (or computational complexity). Computability theory is a vast mathematical subject which studies the ramifications of the concept of computation. It does not deal with the complexity of computation. As your professor mentions, all (Turing-complete) computation models ...

30

(note: the full desciption is a bit complex, and has several subtleties which I prefered to ignore. The following is merely the high-level ideas for the QTM model) When defining a Quantum Turing machine (QTM), one would like to have a simple model, similar to the classical TM (that is, a finite state machine plus an infinite tape), but allow the new model ...

23

The best estimate I know of can be found in Efficient networks for quantum factoring, by David Beckman, Amalavoyal N. Chari, Srikrishna Devabhaktuni, and John Preskill, which gives $72 (\log N)^3$. Having said that, a straight comparison of number of steps on a quantum computer versus number of steps on a classical computer is problematic for various ...

21

Because a quantum computer can be simulated using a classical computer: it's essentially just linear algebra. Given a probability distribution for each of the qubits, you can keep track of how each quantum gate modifies those distributions as time progresses. This isn't very efficient (which is why people want to build actual quantum computers) but it works.

20

As a general preamble, QTMs, TMs and NTMs are all different things (taking huge liberties with a bunch of unspoken assumptions). I'll assume you know what a Turing Machine is. A NTM is a TM where, at any state, with any symbol, the transition function is allowed to have a number of choices of action that is not precisely $1$, i.e. $0$ or more than $1$ (a ...

19

There's no difference in terms of computability. Classical computers can simulate quantum computers. A Turing machine can compute anything that a quantum computer can compute. This isn't some hypothetical point, we simulate quantum computations all the time. You can do it with pen and paper! It's a lot more convenient using one of the many software ...

18

The basic idea is that quantum devices can be in several states at the same time. Typically, a particle can have its spin up and down at the same time. This is called superposition. If you combine n particle, you can have something that can superpose $2^n$ states. Then, if you manage to extend, say, bolean operations to superposed states (or superposed ...

18

Yes, Grover's algorithm shows you can use a quantum algorithm to find an element in an unordered database of size $N$ with high probability by querying the database only $O(\sqrt{N})$ times. Any classical solution that succeeds with high probability requires $\Omega (N)$ queries to the database.

18

First of all it seems that google has exaggerated a little bit by shooting the $10000$ years results. It seems that IBM, on his current and most powerful classic super computer, is able to perform the same task in $2.5$ days, saving the entire search space (Hilbert space) on a $250$ petabytes hard drive. This does not mean that google's result is not to be ...

17

here is a half-baked answer: I know that Ugo Dal Lago at University of Bologna has been studying quantum lambda calculus. You may want to check his publications and perhaps this one in particular: Quantum implicit computational complexity by U. Dal Lago, A. Masini, M. Zorzi. I am saying it's a half-baked answer, because I haven't had chance to read any of ...

17

No implications are known either way: classical simulation of quantum computers tells us nothing about how hard NP search problems are; fast solutions to NP search problems tell us nothing about how fast quantum computers can be simulated classically. The following scenarios are possible: $P=NP=BQP$ $P=NP\subsetneq BQP$ $P\subsetneq NP=BQP$ $P\subsetneq NP\... 17 First of all, quantum computers (or rather, theoretical quantum computation models), are in fact, not more powerful than Turing machines, in the sense that they can be emulated on a Turing machine and can emulate a Turing machine themselves. Note that the article itself doesn't use the word 'computable', and for a good reason. Computability isn't what they'... 14 On the meaning of nondeterminism There are two different meanings of 'nondeterminism' at issue here. Quantum mechanics is usually described as being "not deterministic", but the word "nondeterministic" is used in a specialized way in theoretical computer science. One meaning, which applies to quantum mechanics, is just 'not deterministic'. This is usually ... 14 The other answers are nice, but none address the question: what numeric base(s) might quantum computers use? I will answer in two parts: first, the question is a little subtle, and second, you may use any numeric base, and then you work with qutrits or in general with qudits, which lead to qualitatively new intuitions! Or at any rate, I will try to make the ... 13 What you describe as current computers is known as the von Neumann architecture. This approach is one of many ways to think about classical computation and there are other classical approaches that might or might-not have relevant generalizations to quantum computing. The von Neumann architecture seems to be unlikely to be relevant to quantum computing, due ... 13 Toffoli is universal for classical computation (as shown by @Victor). However, Toffoli is NOT universal for quantum computation (unless we have something crazy like$P = BQP$). To be universal for quantum computation (under the usual definition), the group generated by your gates has to be dense in the unitaries. In other words, given an arbitrary$\...

13

Quantum computers might have some advantage over classical computers for some cases. The most remarkable example is Shor's Algorithm which can factor a large number in polynomial time (while classically, the best known algorithm takes exponential time). This completely breaks schemes like RSA, based on the hardness of factorization. This is not necessarily ...

13

No. Quantum computers cannot solve undecidable problems. A quantum computer can be simulated by a classical computer. So, if a quantum algorithm could solve an undecidable problem, then we could also solve it classically via simulation. However, we already know that if a problem has no classical solution, then it must not have a quantum solution either. ...

13

Destructive interference is the primary thing that makes quantum computers more powerful. In a classical probabilistic computation, having two paths to an output always makes that outcome more likely. In a quantum computer, it can make the outcome less likely. Quantum algorithms are carefully designed so that wrong answers tend to be destructively ...

13

There are many different meanings of the word "can". Is there an algorithm that can break AES-512 encryption? One strategy would be to take all 2^512 possible blocks of 512 bits, encrypt all of them with the public key, and for each of them check whether they match the ciphertext. In a purely abstract sense, this is an algorithm that "can" break AES-512. ...

12

Apologies in advance for the shameless plug, but there is a paper of mine on a quantum lambda calculus that you may find interesting. It is called The Dagger Lambda Calculus and provides a higher-order representation for the diagrammatic circuits that the categorical school of quantum computation have introduced: http://arxiv.org/abs/1406.1633 You can also ...

12

This Quantum Information Science and Technology Roadmapping Project is a very detailed roadmap prepared under ARDA (Advanced Research and Development Activity) around ~2004 with further refinements. Here is the introduction/overview. It had a panel of about 19 elite academic scientists/experts. For a completely contrasting recent overview/review on progress ...

12

Shor's algorithm which puts FACTORING in BQP (bounded error quantum polynomial-time, effectively the quantum equivalent of P) also can be used to solve the DISCRETE LOGARITHM problem, where we want to find an integer $k$ such that $a^{k} = b$ where $a$ and $b$ are given, in (quantum) polynomial time. The DISCRETE LOGARITHM problem has the same status as the ...

12

Most problems that require exponential time on a classical computer also require exponential time on a quantum computer. For example EXPTIME-complete problems will require exponential time on either a classical or a quantum computer. The class of problems solvable in polynomial time on a quantum computer is called BQP. It is believed unlikely that BQP ...

11

Classical computers are already Turing complete, i.e. they can calculate everything that a Turing machine can (a theoretical computer model from Computer Science). According to the Church–Turing thesis Turing completeness includes all functions which can be calculated using any mechanical process. So if this thesis is true, any computer you could possibly ...

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