Questions tagged [classical-computing]
For questions about the relation between quantum computing and classical computing, such as their relative performance.
101
questions
2
votes
2answers
65 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 ...
1
vote
0answers
37 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?
1
vote
1answer
59 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 ...
1
vote
1answer
43 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,...
7
votes
5answers
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 ...
10
votes
1answer
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 ...
4
votes
2answers
96 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 ...
2
votes
0answers
82 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 ...
4
votes
1answer
56 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. ...
3
votes
1answer
95 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 ...
1
vote
1answer
48 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 ...
3
votes
0answers
46 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 ...
7
votes
1answer
312 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 ...
2
votes
0answers
16 views
Are classical analogues of quantum computers using superposed waves possible? [duplicate]
The trick of quantum computing is to take the advantage of wave mechanics (superposition) and entanglement. This allows to perform parallel computations/manipulations with $2^n$ superposed waves for $...
2
votes
2answers
90 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 ...
2
votes
2answers
67 views
How do qubits in quantum computers work? [closed]
I was reading about quantum computers and qubits. While a classical bit can be either 0 or 1, a qubit can be 0 or 1 or both at the same time (can it be none too?). But how is this useful at all?
If it ...
7
votes
1answer
83 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 ...
5
votes
2answers
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 ...
9
votes
5answers
942 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 ...
2
votes
1answer
117 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
2answers
99 views
Question on practical quantum computing programming code [duplicate]
Has anyone tried any quantum computing programming code that shows or demonstrates the advantage of a quantum computer over classical computers? Thanks a lot.
3
votes
2answers
170 views
Does 1 qubit correspond to 2 bits?
In a lot of presentation I always see people say that $n$ qbit are approximately $2^n$ classical bit.
Those talks where oriented for a broad audience, so they left out a lot of things.
Deep down I ...
3
votes
3answers
137 views
Is there an explanation for why, to search through an unstructured database, the average number of checks is $\frac{N}{2}$ in classical computation?
I have came across many books online that all explain that if $N$ is large enough, then the average number of checks in $N/2$ but is there a mathematical explanation or derivation for why this is true?...
2
votes
1answer
65 views
Papers on classical optimization in QAOA
Are there any papers on the classical optimization part of QAOA?
What is the most efficient method now?
And how is the classical optimization classified?
3
votes
0answers
58 views
What is the best way to use loop statements on a quantum computer?
I am interested in solving a time dependent linear partial differential equation of the form $Ax=b$ which, in classical computing, would amount to looping over solutions of $Ax=b$ where $b$ is updated ...
1
vote
0answers
105 views
Can hash functions speed up quantum simulation? (Generalizing May and Schlieper's idea)
Recently May and Schlieper have published a preprint (https://arxiv.org/abs/1905.10074) arguing that the modular exponential register in Shor's algorithms can be replaced with a universally hashed ...
4
votes
2answers
674 views
Can classical linear algebra solvers implement quantum algorithms with similar speed-ups?
A quantum algorithm begins with a register of qubits in an initial state, a unitary operator (the algorithm) manipulates the state of those qubits, and then the state of the qubits is read out (or at ...
2
votes
2answers
166 views
Is it possible to convert classical algorithms to quantum ones?
I am new in this field and I am considering to do research for my engineering degree.
First, I would like to have an opinion from more experienced people. Do you think it is possible to convert ...
0
votes
1answer
51 views
What are some general concepts of how a classical computer would interface with a quantum computer?
Very general question so I'm not looking for an exact answer.
I just want a basic description of certain ways it can be done and then if possible the names of those ways, so that I can look them up ...
3
votes
1answer
64 views
STO-3G Basis Set
Can someone please explain why STO-3G is considered to be a good basis set for quantum computing, while it does not help in classical computing?
I would also be very grateful for any references to ...
7
votes
3answers
322 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$ ...
4
votes
2answers
202 views
How does a classical computer simulate nonclassical correlations?
This may be a dumb question, if so please forgive me, it is late at night.
I have learned that a classical computer can simulate a quantum computer in exponential time and space, but classical ...
3
votes
2answers
314 views
Classical computations from restricted quantum gates
The CNOT gate together with phase shift gates for all possible angles are not universal for quantum computing.
Are they also not universal for classical (reversible) computing?
Is it possible to ...
6
votes
2answers
308 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, ...
5
votes
5answers
249 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 ...
0
votes
1answer
111 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 ...
2
votes
1answer
70 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 ...
2
votes
3answers
65 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 ...
1
vote
1answer
70 views
Will quantum computers pass the Turing test? [closed]
Will quantum computers be able to pass the Turing test sooner than classical computers?
9
votes
1answer
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 ...
12
votes
2answers
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 ...
2
votes
2answers
194 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 ...
2
votes
2answers
62 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 ...
4
votes
1answer
143 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 ...
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
44 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 ...
1
vote
0answers
63 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 ...
4
votes
2answers
72 views
If classical physics emerges in some limit of quantum mechanics, shouldn't there be intermediate classical-quantum computers?
Presumably quantum mechanics really is the way the universe works, and it appears we don't really understand where the boundary between quantum mechanical phenomena like interference end and classical ...
1
vote
1answer
1k views
Quantum computer vs. supercomputer performance [closed]
Does anybody have any other comparisons between a universal quantum computer and a classical computer that might shed some light into how their performance compares?
Below is what I've been able to ...
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 ...
