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


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

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.


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


6

The state of quantum computing technology is still in its infancy, so implementation details are generally important when considering quantum algorithms. Number of gates, number of operations, types of gates (e.g. Clifford vs. non-Clifford) are often necessary information to evaluate the feasibility and value of a quantum algorithm. In many cases quantum ...


5

In classical computing, both circuit diagrams and pseudo-code are used to explain algorithms. The choice between circuits and pseudo-code depends on the context. If the goal is to explain a highly optimized implementation of an algorithm on FPGA, a circuit diagram is probably more suitable. For example, see this paper on AES implementation on FPGA. ...


5

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


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


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

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

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

Quantum computers can leak information to the environment in order to perform non-unitary transformations. The problem is that this irreversibly entangles the computer's state with the environment, i.e. it is equivalent to measuring the qubits that were leaked. This will collapse the state of the computer and prevent the interference effects that are needed ...


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

I believe it is possible to study Quantum Mechanics by studying Quantum Computing. A qubit is a simplest quantum system showing non-classical behavior (superposition of basis states). It is very logical to start studying Quantum Mechanics from the simplest quantum system, and then move to more complex multiqubit systems. If you need Quantum Mechanics to ...


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


2

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


2

Quantum computing does not promise computational speed-ups due to faster clock rates. Rather, the speed-ups are algorithmic. This means that, to achieve the same task (for suitable tasks that allow for this speed-up), quantum computers would need a smaller number of operations to produce an answer. These speed-ups exist even if each "single operation" takes ...


2

There's no straightforward equivalent of the concept of clock rate in quantum computing. Quantum computers are supposed to produce algorithmic speedups only for very specific categories of problems. In simple words, quantum algorithms can be represented by quantum circuits which are basically a sequence of quantum gates. To give you an idea of how quantum ...


2

Quantum computing is not a refinement of classical computing; it's simply a different paradigm of computing aimed at solving specific categories of problems more efficiently. Quantum computing doesn't necessarily require qubits (cf. qudit); that's just a theoretical and experimental convenience. In fact, continuous-variable quantum computing seems to be a ...


2

You're presumably thinking of a spectrum with classical mechanics at one end and quantum mechanics at another, with some hazy "classical-quantum" in between. That's not a great way to think about it. Classical mechanics is more of a practical approximation of quantum mechanics under certain conditions (cf. classical limit), as per the correspondence ...


2

I take your statement that programmers "don't need to know the machinery behind the prevailing paradigm" to mean that most scientific programmers need not know how a $\mathsf{NAND}$ gate is realized, with, say, a set of $6$ or so transistors. However, probably a concept that is fundamental in quantum computing, that can be understood by anyone familiar with ...


2

do we need to come up with completely different quantum-based solutions for such problems, or is there a way to 'interpret' existing algorithms to the quantum domain and still expect some speedup? Generally speaking yes, you need to come up with different algorithms. You cannot simply take a classical algorithm and "quantize it" in a straightforward way. ...


1

The reason that a quantum computer is faster in same tasks is given by different computational paradigm based on quantum mechanics laws. They mainly exploit superposition (i.e. state of qubit is linear combination of zero state and one state) and quantum entanglement (i.e. two or more qubits are connected and they behave as one system, or in other words ...


1

Today many people believe that programming means coding on some language like python; this is not true. The early classical computers were programmed by inserting junctions which connect logical elements of an electronic scheme, and this is also programming. I believe modern programmable quantum computers are programmed like that: a programmer is given a ...


1

(...) depending on what you attempt to compute you "design" your circuit - this is what is called ASSP (Application Specific Signal Processor) where the input is Signal which are processed by the Circuit (processor) to create the processed output - the measure gate. [Source] Reading the question more carefully and after your clarification in the comments, I ...


1

There are no classical registers in Quantum Computing Another contributing factor I believe is that in classical computers you can have a well defined "current state at a given time" (stored notably in CPU registers and DRAM memory in modern systems), and this state changes with time (each CPU clock) in a controlled way. Therefore, it is easier to map ...


1

Qubits are the quantum states that carry the smallest amount of "quantum information": the simplest possible quantum states you can imagine. They are pervasive for this reason, just like bits in classical physics are pervasive because they are the basic unit of information. We use bits all the times simply because we find it convenient to build things (e.g. ...


1

Quantum computers are not just the "conventional computer killer" or a speedy replacement for the conventional computers as you might have assumed in your question. Firstly, some classical tasks that are well suited to quantum computers. They run them really well in a much lesser time. This is because they are able to crunch large numbers using a small ...


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