# Questions tagged [classical-computing]

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

102 questions
Filter by
Sorted by
Tagged with
61 views

### Can error correction for a classical algorithm with bit flips be easier than for a general quantum circuit?

Assume one runs a purely classical algorithm on $n$ logical qubits on a physical device with some bit flip probability. Can implementing error correction in this case be any easier than in the case of ...
89 views

### Are there problems that a classical computer can solve and a quantum computer can never solve?

Apologies if this is a silly question. But I've heard quantum computers can solve problems that classical computers can't. What about the converse, are there any problems that a classical computer can ...
40 views

### Why is sampling considered difficult on a classical computer but easy on a quantum computer? [closed]

It is my understanding that classical computers have a hard time sampling results from an output from a quantum circuit, but quantum computers find it very easy to do so. Why is this?
63 views

### What are the types of models of computation aside from the quantum query model?

It looks like in a lot of quantum algorithms, we use the quantum query model. I wanted to know what are the other types of models of computation, used in quantum computing as well as in classical ...
45 views

### What is the counting argument for the number of elementary operations required for a random function?

What is the counting argument for the following statement (classical)? "A random function on n bits requires $e^{\Omega(n)}$ elementary operations." It appears in the introduction of PRL 116,...
2k 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 ...
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 ...
101 views

### Can the difference between quantum and classical circuits be attributed to different paths in the Hilbert space?

One of the explanations I have encountered for why quantum computation can provide speed-up over the classical is a picture that in the Hilbert space much more paths are allowed quantum-mechanically ...
85 views

### When is a Quantum Computer Slower Than a Classical Computer?

Someone offhandedly mentioned to me that quantum computers are sometimes significantly (I guess they meant asymptotically) slower than classical computers. Unfortunately, I didn't get any arguments ...
58 views

### Quantum computer speedups for classically efficient applications

I'm interested in learning about cases where a quantum computer could be used to perform tasks with only a constant (albeit large) factor of improvement in execution speed over classical computers. ...
125 views

### Using principle of deferred measurement to replace gates conditional on classical bits (c_if)

I am trying to implement the Iterative Phase Estimation algorithm on one of Qiskit's labs. I can do it for a 'nice' phase, such as 1/4 : But if I want to implement the algo generally (as a subroutine ...
65 views

### What's the difference between open-source QRNG and Quantis Device?

qRNG is an open-source quantum random number generator written in python and Quantis RNG is a physical quantum random number generator. Both are capable of generating quantum random numbers, but how ...
48 views

### Shor vs Schnorr: A classical algorithm for breaking RSA? [duplicate]

I am not sure why I haven't heard much chatter about this paper by Dr. Claus Peter Schnorr where he claims to have come up with a classical algorithm to break the RSA protocol. The construction is ...
386 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 ...
17 views

312 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 ...
123 views

### Can I learn Quantum Programming and then go back to learn the Mathematics / Physics behind it later?

Learning from the ground up (while great) is an overdose of the mathematics behind quantum computing and is taking way too long to grasp. I have a Computer Science / Programming background. I am ...
81 views

### CPTP, Kraus representation and classical registers

What is the best mathematical representation of a quantum system that has some classical registers and some quantum registers? I'm asking because I'm considering any "physical" process $\pi()$ that ...
68 views

### What does the $\sqrt{NOT}$ gate have to do with irreversibility?

In his essay "Why now is the right time to study quantum computing" Aram Harrow writes, after describing the action of the $\sqrt{NOT}$ gate, that: However, if we apply $\sqrt{NOT}$ a second time ...
80 views

### Will quantum computers pass the Turing test? [closed]

Will quantum computers be able to pass the Turing test sooner than classical computers?
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 ...
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 ...
231 views

### Does the massive parallelization in Quantum computing imply parallelization of input (as opposed to Turing machine)?

Being a newbie in this field, I'm trying to understand what types of real-life workloads are suitable for migrating to Quantum computers. Intuitively, it seems to me that if a Quantum computer ingests ...
68 views

### Are quantum gates analogous to ASSPs in classical computing?

After reading some with regard to the quantum computing gates and the comparison to classic gates it seems that the quantum computer, at least for the time being, is not viewed as a programmable ...
149 views

### What concepts from classical computing are vital for quantum programmers?

Many scientific programmers get by fine without having a computer science background, i.e. they don't need to know the machinery behind the prevailing paradigm of 0's and 1's (bits), let alone basic ...
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 ...
46 views

### Are binary states (bits) pervasive in classical physics?

If quantum physics is a refinement of classical physics, and quantum computing is a refinement of classical computing, and classical computers use bits (binary digits) whereas quantum computers use ...
68 views

### Can Quantum Voting Machine replace Electronic Voting Machine (EVM) in future?

Some countries like India are using standalone electronic voting machines (EVM) for elections. They are not interconnected, use no power cables (run on battery), no wireless cards and are secure ...