11

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. ...


7

For all we know, it is extraordinarily hard to prove that a problem which can be solved by a quantum computer is classically hard. The reason is that this would solve an important and long-standing open problem in complexity theory, namely whether PSPACE is larger than P. Specifically, any problem which can be solved by a quantum computer in polynomial ...


6

The difficulty with explaining quantum computing is that quantum objects and processes have no direct classical analogue; they're an entirely new ontological category. For example, you might have learned in high school physics that light "is both a particle and a wave" in an attempt to relate it to two classical objects you can intuitively understand. In ...


6

Quantum computers can run classical computations using exactly the same algorithms, and hence have the same running time in terms of scaling. For example, if you look at shor’s algorithm, a major component of that is modular exponentiation, but nobody ever draws the circuit because they just say “use the classical algorithm”. In terms of absolute running ...


5

It isn't really like that, for a few reasons. For the link saying "100 ideal qbits can equate to $2^{100}$ pieces of information", that's talking about logical qbits. Logical qbits are composed of many (perhaps hundreds or even thousands) of physical qbits entangled in a quantum error correction scheme, functioning together as a single qbit. So with 128 ...


5

Scott Aaronson relates quantum and stochastic computation as follows: quantum computation is stochastic computation, but using the 2-norm instead of the 1-norm as the conserved quantity. In both paradigms you form vectors of weighted states, and operate on those vectors using matrices. So they have many similarities. But in stochastic computation the ...


5

A bit, either 0 or 1, can certainly be thought of as a special case of being a qubit. However, that is not to say that anything capable of computing with classical bits is capable of computing with quantum bits. If you have a bit, and don’t know if it’s a 0 or a 1, then how do you describe its state? You have to use Bayesian priors. If you have no idea ...


5

Certainly! Imagine you have $K=2^k$ copies of the search oracle $U_S$ that you can use. Normally, you'd search by iterating the action $$ H^{\otimes n}(\mathbb{I}_n-2|0\rangle\langle 0|^{\otimes n})H^{\otimes n}U_S, $$ starting from an initial state $(H|0\rangle)^{\otimes n}$. This takes time $\Theta(\sqrt{N})$. (I'm using $\mathbb{I}_n$ to denote the $2^n\...


4

I would like to suggest that period finding (a subroutine, if you like, of the famous Shor algorithm) demonstrates a very intuitive, exponential speed-up: It should be intuitively clear that something on the order of (the square root of the uncertainty $\Delta p$) of the period $p$ of function evaluations is required classically to find an unknown period $p$ ...


4

Originally, I misunderstood the question, and was answering a question like "Is it true that quantum computers are necessarily formulated only out of reversible gates?". However, I now understand that the question was intended to be "Must there always be a reversible step inside a quantum computation?" No - there are some computational schemes, such as the ...


4

The two are very different ways of treating calculations. You've probably heard that qbits "can be both 0 and 1 at the same time" or similar; this isn't accomplished by assigning them a value in the domain $[0, 1]$, but rather a linear combination of $0$ and $1$: $\alpha|0\rangle + \beta|1\rangle = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}$ This is ...


4

Your construction by gueswork in this answer is OK but not really elegant. Moreover, it's a convention to start in the state $|0\rangle$; we usually don't initialize a qubit with the state $|1\rangle$. It's better to follow the general construction which I illustrate here. The idea here is to use ancillary qubits and impose unitary evolution on the larger ...


4

First, you need to check if your function is reversible. This determines whether you can perform it inline or not. Your function is not reversible, so we need to perform something like $x, y \rightarrow x, y + f(x)$ instead of $x \rightarrow f(x)$. The great thing about functions of the form $x, y \rightarrow x, y + f(x)$ is that it's very easy to derive a ...


3

Simulating Classical "AND/NAND/OR/NOR/XOR/XNOR" Gates With the help of this answer from Blue, constructing a matrix for a classical gate is just a matter of following the steps. Here is the combined truth table for classical logic gates: $$ \begin{array}{|c|c|c|c|c|c|c|} \hline \text{Input} & \text{AND} & \text{NAND} & \text{OR} & \text{...


3

Simulating "Classical AND Gate" using "Toffoli Gate" (also known as "Controlled-Controlled-NOT Gate", or "CCNOT Gate") With the help of Blue's comment, and the Wikipedia pages here and here, a solution to simulating classical AND gate was found. The CCNOT gate is a 3-qubit gate having the following properties: If both the 1st and 2nd inputs are $\left|1\...


3

How do we know no better classical algorithm exist? We can know thanks to computational complexity theory, which studies the complexity of solving different problems with different computational models. It is in principle possible to prove that no classical algorithm can solve a given problem efficiently. A common way to do it is using reductions, that is, ...


3

100 ideal qubits ... can equate to [$2^n$ pieces of information] This is really not the case. Taking an equivalent line from the same article: To put this all into perspective, 100 normal bits just equals 100 pieces of information, while 100 ideal qubits (qubits we get in a computer simulation: they are perfect and are not influenced by external ...


3

In a sense, if we were doing it in parallel on different nodes, you would save time for running. But if we talk about complexity (that is what we refer to speedup generally), we need a bit of analysis. You agree that we need about $ \sqrt{N} $ operations for the non-parallel case. Say we have two nodes, and we separate the list of N elements into two lists ...


3

Yes, you can encode a program into your qubits in exactly the same way you'd encode a program into bits and then run circuits that interpret the program. One might hope that you could encode the program in some fancy exponentially efficient way, but in Mike&Ike they prove that's not possible. Because there's no exponential advantage, and because the ...


3

No, superposition is not the same as uncertainty about an outcome. If you throw a coin, the state of the coin is not $|0\rangle+|1\rangle$ before landing. If you really want to use the formalism of quantum mechanics to describe the uncertainty about the outcome, you have to describe it as a mixture of the two possible outcomes, that is, something like $|0\...


3

This article seems to adequately explain what you are asking. It shows the growth of usable qubits in quantum computers. So the question comes up whether Moore’s Law can also be applied to quantum qubits. And early evidence suggests that indeed it may [...] The adiabatic line would be a prediction for quantum annealing machines like the D-Wave ...


3

The difficulty with the question is the word intuitive. Intuition basically reflects our understanding of the world around us, which is described by classical physics. Quantum mechanics is exactly the regime where our intuition breaks down because it functions very differently from the world of our everyday experience. As Terry Pratchett said : It’s very ...


3

DaftWullie's comments aren't special to 'efficiently computable' functions $f(x)$ — any function at all which we know how to compute by conventional means, we can compute reversibly with at most a (small!) constant factor overhead. How to reversibly compute a function The proof is simple. For any procedure to compute something conventionally — ...


3

"What feature of a quantum algorithm makes it better than its classical counterpart?" First, a classical algorithm can be thought of a quantum algorithm that makes no use of quantum superpositions. Therefore a quantum algorithm can be at least as good as its classical counterpart. No classical algorithm can be "better" than quantum algorithms can do, ...


2

There is nice example in the Microsoft lecture. Suppose you have a classical black box with 1 input and 1 output. How many queries you need to determine whether the output is constant or variable? Evidently you need 2 queries; first you input 0, second you input 1; if both outputs are identical you have constant, otherwise variable. It turns out that after ...


2

It’s worth stating from the start that “Alice and Bob” scenarios are very different from quantum computation scenarios. The Alice and Bob scenarios are very much that there are two distantly separated locations between which it is impossible to directly perform quantum gates. Meanwhile in the quantum computing architectures you’re talking about, two-qubit ...


2

In 1996, David DiVincenzo listed five key criteria to build a quantum computer: A quantum computer must be scalable, It must be possible to initialise the qubits, Good qubits are needed, the quantum state cannot be lost, We need to have a universal set of quantum gates, We need to be able to measure all qubits. Two additional criteria: The ability to ...


2

You can't ignore the constant factors when comparing quantum computation to classical computation. They're too large. For example, here is an image from some slides I presented last year: The things along the bottom are magic state factories. They have a footprint of 150K physical qubits. Since the AND gate uses 150K qubits for 0.6 milliseconds, we surmise ...


2

There are lots of separate questions in there: politics, physics, etc. and I won't pretend to answer all of it, but let me try to get towards what I think is the core of the matter. How do I explain to the interested non-specialist what I do (the general field)? My explanation actually varies a lot depending on who I'm talking to, and depends a lot on ...


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