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

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

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


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


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

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


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

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


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

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

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

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


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

This section of Nielsen & Chuang is talking specifically about simulating a classical circuit with a quantum circuit using Toffoli gate. So 1) the state $a$ will not be in superposition, since you're simulating a classical circuit and you can't have superposition in a classical circuit; $a$ will always be $|0\rangle$ or $|1\rangle$. 2) you know the ...


2

The linked question in the comments is akin to "can we efficiently simulate a quantum computer without entanglement?", while the question of the OP is more akin to "if we handicap a quantum computer to not use entanglement, is such a quantum computer equivalent to a classical computer?" @DaftWullie's great answer already shows that such a weakened quantum ...


2

Assuming you are talking about starting from a pure state, your statement is true. There are two steps to the proof: Show that a system without entanglement can implement any classical computation. Show that a system that remains separable can be simulated by a classical computation, proving that there are no calculations it can implement that a classical ...


1

You seem to be mixing two very different concepts here. Quantum cloning is talking about the absolute limits of what is theoretically possible in a perfect world. In this absolute theoretical limit, yes we can derive how well quantum cloning can work, and we also know that classical cloning is nominally perfect. There is then a separate question of how well ...


1

I'm confused about what you want to do with a $256\times 256$ matrix of integers $[0,1,\cdots, 255]$. You can create a uniform superposition by Hadamard'ing $24$ separate qubits, and consider your system as the adjacency matrix of a $256$-vertex directed graph, where vertices can be connected with an edge weighted with an integer between $0$ and $2^8-1=255$....


1

Simulating "Classical OR Gate" Please read my answer for simulating "Classical AND Gate" in this post first. In this answer, I am going to use another approach to reach the solution. Let's begin with the table for classical OR gate: $$ \begin{array}{|c|c|} \hline \text{Input} & \text{Output} \\ \hline \begin{array}{cc}0 & 0\end{array} & 0 \...


1

Mathematically I see why the quantum logic gate is reversible, it is a mere unitary operator but on the classical one I don't see where the information is lost, could someone clarify it? For illustration, let's take the classical XOR gate. Say you know that the output or end result of a certain XOR operation is 1. Now what could have been the ...


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