Questions tagged [classical-computing]
For questions about the relation between quantum computing and classical computing, such as their relative performance.
129
questions
3
votes
3
answers
303
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?...
- 31
3
votes
1
answer
83
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?
- 519
3
votes
0
answers
96
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 ...
- 521
1
vote
0
answers
121
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 ...
- 157
4
votes
2
answers
733
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 ...
- 185
3
votes
2
answers
672
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 ...
- 33
0
votes
1
answer
97
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 ...
- 145
5
votes
1
answer
241
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 ...
- 51
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
4
votes
2
answers
235
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 ...
- 441
3
votes
2
answers
343
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 ...
- 133
8
votes
2
answers
365
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, ...
- 207
5
votes
5
answers
546
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 ...
- 111
0
votes
1
answer
165
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
1
answer
136
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 ...
- 626
2
votes
3
answers
83
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 ...
- 245
1
vote
1
answer
114
views
Will quantum computers pass the Turing test? [closed]
Will quantum computers be able to pass the Turing test sooner than classical computers?
user10151
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
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 ...
- 133
4
votes
2
answers
367
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 ...
- 43
2
votes
2
answers
81
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 ...
- 133
4
votes
1
answer
160
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 ...
- 945
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
2
votes
2
answers
104
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 ...
- 945
1
vote
0
answers
76
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 ...
- 171
4
votes
2
answers
104
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 ...
- 141
2
votes
1
answer
2k
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 ...
- 59
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
1
vote
1
answer
89
views
Can quantum computer perform classical computation? [duplicate]
I was going through a paper in which protocol said that the party computes modulo 'd' sum of other party secrets directly. It was not mentioned that the computation is classical. Can I assume that it ...
- 171
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
6
votes
3
answers
865
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}$ ...
- 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
3
votes
1
answer
132
views
Classical and quantum limits to classical copying?
The no-cloning theorem can be sharpened to give quantitative bounds on the fidelity with which an arbitrary quantum state can be copied. Is there a similar picture available for classical copying? ...
- 131
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
1
vote
0
answers
593
views
Comparing CPU to QPU In terms of processing power
The current processors are limited by the speed of the electrons but quantum processors take advantage of the properties of subatomic particles. But the question is how to compare the processing power ...
- 209
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
5
votes
2
answers
328
views
References on quantum arithmetic circuit complexity
In classical computing, arithmetic circuit complexity is apparently a big topic. But I couldn't find much about the complexity of quantum arithmetic circuits. Almost all references like arXiv:1805....
- 16.9k
1
vote
1
answer
121
views
Implementing piecewise functions on a quantum computer
I am curious about how to do implement functions like $$f(x)=\begin{cases}
2x &\text{if} &0\leq x <0.5 \\
x/2 &\text{if} &0.5\leq x<1
\end{cases}$$
Do we implement this like ...
- 1,400
-1
votes
1
answer
160
views
Large size of matrices for little outcome [closed]
I am stuck in a dilemma about how to proceed with a quantum computing algorithm that changes the original state of a system to another.
Say I have a superposition of all $8$ bit integer values that ...
- 1,400
2
votes
1
answer
119
views
Is it possible to construct an equivalent quantum circuit from a CORDIC-based digital circuit?
DaftWullie mentions an interesting point here:
let's assume that we know an efficient classical computation of $f(x)$. That means we can build a reversible quantum computation that runs in the same ...
- 16.9k
1
vote
0
answers
65
views
What is the difference in computational power between qubit and bit (transistor)? [duplicate]
If I use for example 5-qubit IBM-Q quantum computer and we accept the law of quantum parallelism ($n$ qubit = $2^n$ ordinary bits), so does it mean that computational power of this computer is equal ...
- 113
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&...
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
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
6
votes
2
answers
606
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 ...
- 63
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 ...
13
votes
2
answers
427
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 ...
- 238
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
4
votes
1
answer
146
views
Could we use varying voltage with programmable gates?
One of the benefits I'm reading about qubits is that they can be in an infinite number of states. I'm aware of Holevo's bound (even though I don't fully understand it). However, it made me think of ...
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