Questions tagged [classical-computing]
For questions about the relation between quantum computing and classical computing, such as their relative performance.
40
questions
35
votes
6
answers
2k
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 ...
- 1,079
8
votes
3
answers
2k
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?
- 641
177
votes
13
answers
40k
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 ...
- 1,622
36
votes
3
answers
3k
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 ...
- 610
47
votes
2
answers
7k
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'....
- 3,074
29
votes
5
answers
8k
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?
- 633
10
votes
3
answers
790
views
What is the simplest algorithm to demonstrate intuitively 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 ...
- 1,079
17
votes
4
answers
9k
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&...
27
votes
4
answers
6k
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' ...
- 371
8
votes
2
answers
639
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 ...
- 241
7
votes
2
answers
386
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?
- 71
2
votes
4
answers
3k
views
Why do computer scientists care about the phase of qubits?
When I design some classical register, flip-flop, binary counter, small byte of RAM, etc from scratch with classical logic gate, I never deal with such binary direction because classical bit doesn't ...
23
votes
3
answers
5k
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 ...
- 333
20
votes
2
answers
933
views
Is it possible to "calculate" the absolute value of a permanent using Boson Sampling?
In boson sampling, if we start with 1 photon in each of the first $M$ modes of an interferometer, the probability of detecting 1 photon in each output mode is: $|\textrm{Perm}(A)|^2$, where the ...
- 12.8k
8
votes
3
answers
809
views
Compiling a classical function to a quantum circuit in practice
It can be shown that any classical function $f$ can be implemented by a quantum circuit $Q_f$, so that
$$
\sum_{x}|x,0^k\rangle \xrightarrow{\mathit{Q_f}} \sum_{x}|x,f(x)\rangle
$$
where $f$ has $k$ ...
- 81
8
votes
1
answer
780
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 ...
- 13.1k
6
votes
1
answer
195
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.
- 12.8k
3
votes
1
answer
1k
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 ...
- 798
17
votes
2
answers
676
views
In a Quantum Turing Machine, how is the decision to move along the memory tape made?
Let, for a Quantum Turing machine (QTM), the state set be $Q$, and the alphabet of symbols be $\sum=\{0,1\}$, which appear at the tape head. Then, as per my understanding, at any given time while the ...
- 223
16
votes
4
answers
4k
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 ...
- 945
15
votes
4
answers
888
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 ...
- 3,074
12
votes
2
answers
820
views
Can we speed up the Grover's Algorithm by running parallel processes?
In classical computing, we can run the key search (for example AES) by running parallel computing nodes as many as possible.
It is clear that we can run many Grover's algorithms, too.
My question is;...
- 689
12
votes
1
answer
2k
views
Are circuits with more than 1000 gates common?
I have seen circuits with 30 qubits and around 500 gates. Also circuits with 32 qubits and 6000 gates. Are circuits with more than 1000 gates common in quantum computing? Are there many quantum ...
- 131
9
votes
1
answer
3k
views
Is there anything that can be programmed on a classical computer but not on a quantum computer?
Would we need to create new algorithms that only work on quantum computers or would be simply edit codes in languages such as C++ to involve the new primitives from quantum computing? Are there ...
user10151
9
votes
5
answers
1k
views
If quantum computing always return random measurement (or uncertain measurement), why do we still need it?
I am very new to quantum computing and currently studying quantum computing on my own through various resources (Youtube Qiskit, Qiskit website, book).
As my mindset is still "locked" with ...
- 93
9
votes
4
answers
4k
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 ...
- 203
8
votes
5
answers
3k
views
Why can't quantum computation replace classical computation?
I am not a total novice of quantum computation (have read the first 6 chapters of Nielsen and Chuang, though not familiar with every part), but there are some fundamental questions that I don't know ...
- 81
8
votes
1
answer
413
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 ...
- 744
7
votes
3
answers
201
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 ...
- 3,074
6
votes
1
answer
228
views
What is the relationship between the size of the Hilbert space for boson sampling and the complexity of classical simulating it?
My intuition is that the fastest classical algorithm for simulating some kind of noiseless quantum sampling process should scale roughly with the dimension of the Hilbert space: you would need to ...
- 2,357
5
votes
2
answers
245
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 ...
- 790
4
votes
1
answer
152
views
Will standard programming languages be applicable for quantum computing?
I'm new to quantum computers and computing, so it's possible my question is pointless or unnecessary ... but what about current programming languages such as Java, C++, Python in terms of quantum ...
- 173
3
votes
2
answers
2k
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 ...
- 652
3
votes
1
answer
1k
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 ...
- 133
3
votes
1
answer
159
views
How can classical computations be non-unitary?
Given that classical physics emerges from quantum physics on a macroscopic scale, and all quantum operators are unitary, how are we able to perform non-unitary operations (such as setting a register ...
- 397
3
votes
1
answer
151
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 ...
- 16.9k
2
votes
1
answer
589
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
1
answer
252
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 ...
- 171
2
votes
2
answers
177
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 ...
- 1,079
1
vote
2
answers
254
views
Is there any real world problem where I can see quantum computing being better than classical computing?
Is there any paper or piece of code showing, on a REAL quantum computer, that a specific real world problem (possibly related to computer science, machine learning or finance and possibly NOT related ...
- 487