Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
179 votes
13 answers
42k 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 ...
John Duffield's user avatar
50 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'....
Discrete lizard's user avatar
43 votes
7 answers
8k views

Why is it harder to build quantum computers than classical computers?

Is it because we don't know exactly how to create quantum computers (and how they must work), or do we know how to create it in theory, but don't have the tools to execute it in practice? Is it a mix ...
Archil Zhvania's user avatar
37 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 ...
Steven Sagona's user avatar
37 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 ...
Glorfindel's user avatar
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?
Alex Jone's user avatar
  • 633
29 votes
4 answers
7k 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' ...
Philip Oakley's user avatar
25 votes
3 answers
6k 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 ...
Paul Turner's user avatar
24 votes
3 answers
3k views

Is quantum cryptography safer than classical cryptography?

Quantum computing allows us to encrypt information in a different way compared to what we use today, but quantum computers are much more powerful than today's computers. So if we manage to build ...
Archil Zhvania's user avatar
20 votes
3 answers
1k 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 ...
user1271772 No more free time's user avatar
18 votes
4 answers
12k 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&...
Siu Ching Pong -Asuka Kenji-'s user avatar
17 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 ...
develarist's user avatar
17 votes
2 answers
703 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 ...
Prem's user avatar
  • 223
14 votes
4 answers
945 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 ...
Discrete lizard's user avatar
13 votes
2 answers
2k views

Does quantum computing already possess the level of abstraction to be explicable even without knowledge of physics?

Currently, quantum computer science (in contrast to classical computer science) can mostly only be understood if one has a good inside knowledge of physics, or more precisely quantum physics. Only ...
Tetragrammaton's user avatar
13 votes
2 answers
484 views

Quantum Supremacy: How do we know that a better classical algorithm doesn't exist?

According to the Wikipedia (Which quotes this paper https://arxiv.org/abs/1203.5813 by Preskill) the definition of Quantum Supremacy is Quantum supremacy or quantum advantage is the potential ...
P. C. Spaniel's user avatar
13 votes
2 answers
996 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;...
kelalaka's user avatar
  • 709
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 ...
Alejandro Arcila's user avatar
11 votes
1 answer
241 views

Quantum memory assisting classical memory

Consider a classical computer, one making, say, a calculation involving a large amount of data. Would quantum memory allow it to store that information (in the short term) more efficiently, or better ...
auden's user avatar
  • 3,459
10 votes
3 answers
877 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 ...
Steven Sagona's user avatar
9 votes
5 answers
2k 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 ...
KamWoh Ng's user avatar
9 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 ...
Liren Lin's user avatar
  • 191
9 votes
3 answers
463 views

What is quantum computing vs. what is not quantum computing

That is to say, what are some common or popular misconceptions about what constitutes quantum computing? and how are those things misconceptions? It could help in explaining to frame this while ...
PowerLuser's user avatar
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 ...
user avatar
9 votes
4 answers
5k 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 ...
zomega's user avatar
  • 203
9 votes
2 answers
436 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?
Adou's user avatar
  • 91
9 votes
1 answer
993 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 ...
Martin Vesely's user avatar
9 votes
2 answers
478 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 ...
fr_andres's user avatar
  • 754
9 votes
1 answer
122 views

Can a stored programming model be applied to a Quantum Computer?

A stored programming computer model is that where a central memory is used to store both instructions and data that they operate on. Basically all the classical computers of today that follow the von ...
K Sarkar's user avatar
  • 171
8 votes
2 answers
1k views

The process for transferring qubits between locations

I understand that right now qubits are physical entities in a Quantum Computer and I am playing around on the IBM Quantum Computer as well as the Q# language and dipping my toes into the Quantum world ...
Leigh Griffin's user avatar
8 votes
2 answers
383 views

Is it right to think of superposition as just angle?

Based on my current understanding, a qubit is represented as a vector $(a, b)$ which satisfy $a^2 + b^2 = 1$. Classical bit one can be represented as $(0, 1)$ and bit zero can be represented as $(1, ...
Wong Jia Hau's user avatar
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?
Tobias Fritzn's user avatar
8 votes
2 answers
946 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 ...
J. Doe's user avatar
  • 241
8 votes
1 answer
183 views

Is there a fast sparse Hadamard transform?

Suppose I give you an $n$-qubit state vector as a classical list of numbers (or as an oracle that can query the amplitudes). I tell you this state vector will contain exactly $k$ non-zero amplitudes, ...
Craig Gidney's user avatar
  • 37.7k
8 votes
3 answers
1k 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$ ...
kgi's user avatar
  • 81
8 votes
0 answers
140 views

Empirical Algorithmics for Near-Term Quantum Computing

In Empirical Algorithmics, researchers aim to understand the performance of algorithms through analyzing their empirical performance. This is quite common in machine learning and optimization. Right ...
hopefully coherent's user avatar
7 votes
3 answers
222 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 ...
Discrete lizard's user avatar
7 votes
1 answer
165 views

what matrix operations have better known time complexity on a quantum computer?

I'm exploring quantum computers for a semester project. I'm mainly interested in making faster matrix calculations than a regular computer. I was wondering what arithmetic operations (irrespective of ...
adiboi's user avatar
  • 71
7 votes
1 answer
213 views

Circuit from finite group of gates and classical simulations

Let $ G $ be a finite group of quantum gates. Is it true that any circuit made using only gates from the finite group $ G $ can be efficiently simulated on a classical computer? Here by circuit made ...
Ian Gershon Teixeira's user avatar
7 votes
1 answer
324 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 ...
tparker's user avatar
  • 2,801
6 votes
2 answers
2k views

Aren't qubits just ternary?

Qubits have 3 states: 1, 0, and 1 and 0 at the same time. If a qubit can have 3 states, then how come they are seen as different from ternary computing, which also has 3 states? Is it that the 3 ...
jort57's user avatar
  • 83
6 votes
5 answers
662 views

Does a classical computer really require $2^n$ complex numbers to represent the state of $n$ qubit quantum computer?

One often reads that the key reason why classical computers (probabilistic or deterministic) are unable to simulate quantum algorithms such as Simon's or Shor's efficiently is that a classical ...
QC-Novice's user avatar
  • 121
6 votes
2 answers
756 views

Does quantum computing relate to stochastic computing in any way?

I'm a bit familiar with the concept of stochastic computing, where numbers are stored in large bit streams called "Stochastic Numbers", which represent numbers in the domain $[0,1]$ typically. The ...
DanBC's user avatar
  • 63
6 votes
1 answer
71 views

Assessing speed-up via Quantum-Stochastic correspondence

You can make a natural correspondence between a quantum state vector and a classical probability vector, and between a quantum unitary operator and a classical stochastic matrix. There is also a ...
hopefully coherent's user avatar
6 votes
3 answers
216 views

Will Moore's Law be no longer effective once quantum computers are created? [duplicate]

Moore's law states that computer power doubles in every 18 months (more formally: "the number of transistors in a dense integrated circuit doubles about every two years."). Statistics suggest that ...
Archil Zhvania's user avatar
6 votes
1 answer
212 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.
user1271772 No more free time's user avatar
6 votes
2 answers
583 views

Can classical algorithms be improved by using quantum simulation as an intermediary step?

I'm wondering whether even if we cannot create a fast quantum computer, simulating quantum algorithms can be a reasonable method for classical algorithms. In particular, I'd like to see any results ...
Discrete lizard's user avatar
6 votes
3 answers
1k views

Are there many practical problems for which Grover's algorithm beats the best heuristic classical algorithm?

It's well known that, given an oracle for a function $f$ from a very large set $S$ (of order $N \gg 1$) to $\{0, 1\}$, Grover's algorithm can find an element of $S$ that maps to 1 with $\sim \sqrt{N}$ ...
tparker's user avatar
  • 2,801
5 votes
4 answers
4k 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 ...
Muhammad Ikhwan Perwira's user avatar
5 votes
3 answers
3k views

Why do classical bits perform calculations at a scale that expands linearly and qubits at exponential scale in the number of (qu)bits?

What does one mean by saying that classical bits perform operations at the scale of $2n$ and quantum computers perform operations at the scale of $2^n$? In both cases, $n$ = Number of bits/qubits.
crazy  lizard's user avatar