86

I'll be trying to approach this from a neutral point of view. Your question is sort of "opinion-based", but yet, there are a few important points to be made. Theoretically, there's no convincing argument (yet) as to why quantum computers aren't practically realizable. But, do check out: How Quantum Computers Fail: Quantum Codes, Correlations in Physical ...


34

We know exactly, in theory, how to construct a quantum computer. But that is intrinsically more difficult than to construct a classical computer. In a classical computer, you do not have to use a single particle to encode bits. Instead, you might say that anything less than a billion electrons is a 0 and anything more than that is a 1, and aim for, say, two ...


33

Classical computing has been around longer than quantum computing. The early days of classical computing is similar to what we are experiencing now with quantum computing. The Z3 (First Turing complete electronic device) built in the 1940s was the size of a room and less powerful than your phone. This speaks to the phenomenal progress we have experienced in ...


26

There is still a search for problems where the D-Wave shows improvement over classical algorithms. One might recall media splashes where the D-Wave solved some instances $10^8$ times faster than a classical algorithms but forgot to mention that the problem can be solved in polynomial time using minimum weight perfect matching. Denchev showing $10^8$ ...


26

Is quantum computing just pie in the sky? So far it is looking this way. We have been reaching for this pie aggressively over the last three decades but with not much success. we do have quantum computers now, but they are not the pie we wanted, which is a quantum computer that can actually solve a problem faster or with better energetic efficiency than a ...


23

If you take as definition "the number of transistors in a dense integrated circuit doubles about every two years", it definitely does not apply: as answered here in Do the 'fundamental circuit elements' have a correspondence in quantum technologies? there exist no transistors-as-fundamental-components (nor do exist fundamental-parallel-to-transistors) in a ...


17

Early classical computers were built with existing technology. For example, vacuum tubes were invented around four decades before they were used to make Colossus. For quantum computers, we need to invent the technology before we make the computer. And the technology is so beyond what had previous existed, that just this step has taken a few decades. Now we ...


16

If you are talking specifically about quantum key distribution (quantum cryptography being an umbrella term that could apply to lots of stuff), then once we have a quantum key distribution scheme, this is theoretically perfectly secure. Rather than computational security that much of current cryptography is based on, quantum key distribution is perfectly ...


15

TL,DR: Engineering and physics arguments have already been made. I add a historical perspective: I argue that the field of quantum computation is really only a bit more than two decades old and that it took us more than three decades to build something like the MU5. Since you mention the timeline, let's have a closer look: The beginnings First of all, the ...


13

When you ask whether it is pie in the sky, that rather depends on what promises you think quantum technologies are trying to fulfil. And that depends on who the people are making those promises. Consider why you are even aware of quantum computation, given that it hasn't yet managed to produce any devices (or to be more fair, not very many devices) which ...


13

You might find this analogy helpful: the development of quantum algorithms is still in the Booth's multiplication algorithm stage; we haven't quite reached dynamic programming or backtracking. You'll find that most textbooks explain the Booth's algorithm using the following circuit. That is in fact, the method in which the multiplication logic is ...


12

The short answer $\newcommand{\modN}[1]{#1\,\operatorname{mod}\,N}\newcommand{\on}[1]{\operatorname{#1}}$Quantum Computers are able to run subroutines of an algorithm for factoring, exponentially faster than any known classical counterpart. This doesn't mean classical computers CAN'T do it fast too, we just don't know as of today a way for classical ...


12

You are totally right in your assumption about transporting qubits from Alice to Bob implies something physical. Usually problems/situations that have this setup of a transmission between two parties are called quantum communications. These problems/situations sometimes disambiguate by calling their qubits "flying qubits" which are almost always photons. ...


11

There's many reasons, both in theory and implementation, that make quantum computers much harder to build. The simplest might be this: while it is easy to build machines that exhibit classical behaviour, demonstrations of quantum behaviour require really cold and really precisely controlled machines. The thermodynamic conditions of the quantum regime are ...


11

To answer part of the question, "will I ever buy a quantum computer", etc. I think there is a fundamental misunderstanding. Quantum computing isn't just classical computing but faster. A quantum computer solves certain kinds of problems in a short time that would take a classical super computer a thousand years. This isn't an exaggeration. But regular kinds ...


10

In summary, no. If you think about it, this makes sense. When measuring a quantum system with $n$ qubits, you get $n$ bits of information. the $2^n$ figure exists only when the system is in superposition, which a classical computer cannot access. The specific theorem in question here is Holevo's theorem. To quote Wikipedia: In essence, the Holevo bound ...


10

TL;DR: I've been working on the theory of quantum computers for about 15 years. I've seen nothing convincing to say that they won't work. Of course, the only real proof that they can work is to make one. It's happening now. However, what a quantum computer will do and why we want it does not match up with the public perception. Is quantum computing just ...


10

Your primary assertion that the mathematics of waves mimic that of quantum mechanics is the right one. In fact, many of the pioneers of QM used to refer to it as wave mechanics for this precise reason. Then it is natural to ask, " Why can't we do quantum computing with waves ?". The short answer is that quantum mechanics allows us to work with an ...


10

Short answer: no. Any classical algorithm can be transformed into quantum algorithm. This result has little practical value, because you don't obtain quantum speedup, but it is important from theoretical point of view.


9

The common Computer Science usage of 'ignoring constants' is only useful where the differences in performance of various kinds of hardware architecture or software can be ignored with a little bit of massaging. But even in classical computation, it is important to be aware of the impact of architecture (caching behaviour, hard disk usage) if you want to ...


9

Most attacks now on classical computers don't actually break the encryption, they trick the systems / communication protocols into using it in a weak way, or into exposing information via side channels or directly (via exploits like buffer overflows). Or they trick humans into doing something (social engineering). I.e. currently you don't attack the crypto ...


9

Here is a quick list of notable differences between analog and quantum computers: Analog computers can't pass Bell tests. The state space of an analog computer with N sliders is N dimensional. The state space of a quantum computer with N qubits is $2^N$ dimensional. Error correct an analog computer and what you've got is a digital computer (i.e. not ...


9

I don't think you need to know quantum physics to understand quantum computing - similarly to how you don't think about the hardware implementation of the classical computers when you write high-level code for them. The field of quantum computing has grown to the point where one cannot really teach all of it in one course, so different approaches to ...


8

tl;dr- Moore's law won't necessarily apply to the quantum computing industry. A deciding factor may be if the manufacturing processes can be iteratively improved to exponentially increase something analogous to transistor count or roughly proportional to performance. Background: Moore's law and why it worked It's important to note that Moore's law was ...


8

Why would you expect two different technologies to advance at the same rate? Simply put, quantum computers can be immensely more powerful but are immensely harder to build than classical computers. The theory of their operation is more complicated and based on recent physics, there are greater theoretical pitfalls and obstacles that inhibit their scaling up ...


8

See the timeline on Wikipedia, and ask yourself where's the parallel adder? It seems to me that your answer lies in your question. Looking at the timeline on Wikipedia shows very slow progress from 1959 until about 2009. It was mainly theoretical work until we went from zero to one. In the only 9 years since then, the pace of progress has been ...


7

It appears to be true, up to a point. As I read Scott Aaronson's paper, it says that if you start with 1 photon in each of the first $M$ modes of an interferometer, and find the probability $P_S$ that a set $s_i$ photons is output in each mode $i\in\{1,\ldots, N\}$ where $\sum_is_i=M$, is $$ P_s=\frac{|\text{Per(A)}|^2}{s_1!s_2!\ldots s_M!}. $$ So, indeed, ...


7

If we have a QTM with state set $Q$ and a tape alphabet $\Sigma = \{0,1\}$, we cannot say that the qubit being scanned by the tape head "holds" a vector $a|0\rangle + b|1\rangle$ or that the (internal) state is a vector with basis states corresponding to $Q$. The qubits on the tape can be correlated with one another and with the internal state, as well as ...


7

I'm not sure it really is true to make such a claim, even though it is one that is often seen. Even so, this statement is common because it does point towards a difference between classical computers and quantum ones. Classical computation is essentially a process that takes a single input bit string and keeps transforming it until you get a single output ...


7

The sad truth for most of the people here is that John Duffield (the asker) is right. There is no proof that a quantum computer will ever be of any value. However, for the companies that have invested in quantum computing (IBM, Google, Intel, Microsoft, etc.), it is entirely worth it to try to build one, because if they are successful they will be able to ...


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