Questions tagged [classical-computing]

For questions about the relation between quantum computing and classical computing, such as their relative performance.

Filter by
Sorted by
Tagged with
26
votes
6answers
1k views

If quantum speed-up is due to the wave-like nature of quantum mechanics, why not just use regular waves?

The intuition I have for why quantum computing can perform better than classical computing is that the wavelike nature of wavefunctions allow you to interfere multiple states of information with a ...
32
votes
3answers
2k views

Can a quantum computer simulate a normal computer?

Similar to the question Could a Turing Machine simulate a quantum computer?: given a 'classical' algorithm, is it always possible to formulate an equivalent algorithm which can be performed on a ...
155
votes
13answers
36k views

Is quantum computing just pie in the sky?

I have a computer science degree. I work in IT, and have done so for many years. In that period "classical" computers have advanced by leaps and bounds. I now have a terabyte disk drive in my bedroom ...
26
votes
5answers
7k views

Does Moore's law apply to quantum computing?

Plain and simple. Does Moore's law apply to quantum computing, or is it similar but with the numbers adjusted (ex. triples every 2 years). Also, if Moore's law doesn't apply, why do qubits change it?
6
votes
2answers
657 views

What exactly makes quantum computers faster than classical computers?

What feature of a quantum algorithm makes it better than its classical counterpart? Are quantum computers faster than classical ones in all respects?
44
votes
2answers
6k views

Is there proof that the D-wave (one) is a quantum computer and is effective?

I'm admittedly a novice in this field, but I have read that, while the D-wave (one) is an interesting device, there is some skepticism regarding it being 1) useful and 2) actually a 'quantum computer'....
8
votes
3answers
601 views

Simplest algorithm for intuitively demonstrating quantum speed-up?

What's the simplest algorithm (like Deutsch's algorithm and Grover's Algorithm) for intuitively demonstrating quantum speed-up? And can this algorithm be explained intuitively? Ideally this would be ...
12
votes
4answers
4k views

Implementing “Classical AND Gate” and “Classical OR Gate” with a quantum circuit

Quantum cNOT Gate (Classical XOR Gate) A "Controlled NOT (cNOT) Gate" flips the 2nd qubit if the 1st qubit is $\left|1\right>$, and returns the 2nd qubit as-is if the 1st qubit is $\left|0\right&...
7
votes
2answers
336 views

Understanding (theoretical) computing power of quantum computers

I am very new to quantum computing and just try to understand things from a computer scientist's perspective. In terms of computational power, what I have understood, 100 ideal qubits ... can ...
7
votes
2answers
303 views

Are we certain that quantum computers are more efficient than classical computers can be built?

I mean are we certain that they will be able to provide us a huge improvements (in some tasks) compared to clasical computers?
21
votes
3answers
3k views

What makes quantum computers so good at computing prime factors?

One of the common claims about quantum computers is their ability to "break" conventional cryptography. This is because conventional cryptography is based on prime factors, something which is ...
6
votes
1answer
155 views

What classical public key cryptography protocols exist for which hacking is QMA complete or QMA hard?

Such a public key cryptosystem would be "quantum safe" in the sense that quantum computers cannot efficiently solve QMA hard problems.
7
votes
1answer
259 views

Classical algorithm with complexity similar to Shor's discovered: Are there more efficient quantum algorithms than Shor's?

In the article Fast Factoring Integers by SVP Algorithms the author claims that he discovered classical algorithm for factoring integers in polynomial time. The Quantum Report mentioned here that it ...
1
vote
1answer
600 views

Reversibility and irreversibility of logic gates (quantum vs classical)

I have been told that one of the great keys that unlock quantum computing's potential is the reversibility of quantum logic gates as for classical gates there's some loss of information, but I cannot ...
13
votes
4answers
3k views

Quantum circuits explain algorithms, why didn't classical circuits?

When explaining a quantum algorithm, many revert to 'circuit-speak' by drawing a diagram of how qubits split off into transformations and measurements, however, rarely if not never would someone ...
2
votes
2answers
1k views

How much memory is required to simulate a 48-qubit circuit?

This CDMTCS Report 514, 2017 entitled "The Road to Quantum Computational Supremacy" states (in Section 6) that the amount of memory needed to simulate random quantum circuits on classical computers ...
19
votes
4answers
3k views

Are quantum computers just a variant on Analog computers of the 50's & 60's that many have never seen nor used?

In the recent Question "Is Quantum Computing just Pie in the Sky" there are many responses regarding the improvements in quantum capabilities, however all are focussed on the current 'digital' ...
15
votes
4answers
724 views

Is the common Computer Science usage of 'ignoring constants' useful when comparing classical computing with quantum computing?

Daniel Sank mentioned in a comment, responding to (my) opinion that the constant speed-up of $10^8$ on a problem admitting a polynomial time algorithm is meager, that Complexity theory is way too ...
8
votes
1answer
288 views

How does the Curry-Howard correspondence apply to quantum programs?

In words of Wikipedia, The Curry–Howard correspondence is the observation that two families of seemingly unrelated formalisms—namely, the proof systems on one hand, and the models of computation ...
7
votes
4answers
2k views

Does a quantum computer have a clock signal and if yes how big is it?

I think there can't be a computer running software without having a clock signal. A fast classical computer has a clock rate between 4 to 5 GHz. If quantum computers are so much faster they must have ...
7
votes
3answers
177 views

Can the theory of quantum computation assist in the miniaturization of transistors?

In his inaugural lecture, Ronald de Wolf states People are working with quantum objects, but trying to make them behave as classical as possible. (...) Instead of suppressing them to make systems ...
5
votes
2answers
186 views

A quantum computer that doesn't use entangled qubits has the same computational power as a classical one?

Is the statement in the question correct? I would love to receive an explanation as to why it is or isn't. I have a computer science degree background and I am a beginner learning the fundamental of ...
3
votes
1answer
656 views

Can a quantum computer run classical algorithms?

I realize that fundamentally speaking quantum and classical computers might as well be apples and oranges, and that for very specific problems such as integer factorization with Shor's algorithm ...
3
votes
1answer
95 views

No. of bits in 160 qubits computer [duplicate]

I read in a book that (https://hub.packtpub.com/quantum-expert-robert-sutor-explains-the-basics-of-quantum-computing/) 160 qubits (quantum bits) could hold $2^{160} \approx1.46\times 10^{48}$ bits ...
3
votes
1answer
111 views

Aren't reversible logic gates a necessity for efficiently executing quantum algorithms?

The Wikipedia article on logical reversibility says: ...reversible logic gates offered practical improvements of bit-manipulation transforms in cryptography and computer graphics. But I guess ...
2
votes
1answer
320 views

FANOUT with Toffoli Gate

Figure 1.16: FANOUT with the Toffoli gate, with the second bit being the input to the FANOUT (and the other two bits standard ancilla states), and the output from the FANOUT appearing on the second ...
2
votes
2answers
87 views

Generally speaking, are quantum speedups always due to parallelization of a given problem?

We know that quantum computers use the wave-like nature of quantum mechanics to perform interference. Sometimes we can use this interference to perform specific algorithms that will cause enough ...