Questions tagged [classical-computing]
For questions about the relation between quantum computing and classical computing, such as their relative performance.
130
questions
0
votes
1
answer
345
views
Can a quantum computer count up by 1 faster than a classical computer?
Let's say you want to generate all images of size NxN, black/white pixels.
This is equivalent to counting from 0 to 2^(N^2)-1.
...
glS♦
- 21.7k
1
vote
1
answer
75
views
Accuracy of Classical Counting problem
Consider a classical algorithm for the counting problem which samples uniformly and
independently $k$ times from the search space, and let $X_1, ... ,X_k$ be the results of
the oracle calls, that is, $...
CommunityBot
- 1
1
vote
2
answers
55
views
Can a classical circuit of size $2^k$ be modelled by a quantum circuit of size $k$ or vice versa?
There is something fundamental I don’t understand about quantum computing and hence the following question may be very trivial or stupid for which I apologize in advance.
A boolean function $f:\{0,1\}^...
- 1,812
0
votes
1
answer
88
views
Deutsch-Jozsa Algorithm - classical solution
so I'm self-studying quantum computing and have a question about the proposed classical solution to the Deustch-Jozsa problem.
So given your function $f: \{0,1\}^n \rightarrow \{0,1\}$ say you were to ...
- 2,258
0
votes
0
answers
30
views
What is reservoir computing in simple terms, and how can it be used with quantum computing?
For those who are familiar with the notion of Reservoir Computing, can you explain the concept with simple terms and how it can be used with quantum computing ?
glS♦
- 21.7k
1
vote
0
answers
28
views
Find the minimal and maximal of $\widehat{S}_f (\rho \| U^* \sigma U)$
I have been study the minimal (maximal) of a $f-$divergence. Fumio Hiai introduced the $\widehat{S}_f (\rho \| \sigma)$ divergence in his article.
$$\widehat{S}_f (\rho \| \sigma) := \text{Tr} \sigma^{...
- 111
3
votes
0
answers
76
views
Understanding the Gottesman-Knill Theorem
I come from a theoretical CS background, and I am trying to gain a better appreciation of the exact formal statement of the Gottesman-Knill theorem in terms that I am more familiar with. My question ...
- 397
2
votes
1
answer
60
views
Where is "quantum search" in the complexity hierarchy?
Grover's algorithm is one of the most popular quantum algorithms that solves the problem of "quantum search." But what is this problem, and what are its characteristics.
When considering ...
- 9,346
2
votes
1
answer
97
views
Is there something wrong with cross-entropy benchmarking, or is it still considered as a reasonable path towards quantum supremacy?
My question is strongly related with this one. Google's quantum supremacy claim uses Random Circuit Sampling. The principle is the following one: a realistic noise model for random circuits performed ...
- 9,346
6
votes
3
answers
864
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}$ ...
3
votes
1
answer
189
views
How does one convert a truth table to a square permutation matrix?
Given a classical circuit of $m$ inputs and $n$ outputs, composed of various AND gates, OR gates, NOT gates, etc., a truth table is a $2^{m}\times(m+n)$-sized matrix, where, in general, the first $m$ ...
- 1,058
0
votes
0
answers
24
views
Applying a clock in quantum computing?
In quantum computing, I feel it mostly looks like designing hardware with Hardware Description Language (HDL) experience such as VHDL or Verilog.
So the term program language for quantum computing ...
2
votes
3
answers
1k
views
Why do people say that Grover's algorithm does not parallelize well?
I've seen several sources, including NIST, claim that Grover's algorithm is unlikely to be useful for attacking a symmetric-key algorithm like AES-128 or a hashing algorithm because "Grover's ...
- 1,812
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 ...
CommunityBot
- 1
43
votes
7
answers
7k
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 ...
CommunityBot
- 1
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 ...
- 16.9k
0
votes
0
answers
24
views
Mapping a classical cipher into quantum implementation of Grover Oracle
I am translating simple ciphers into quantum implementation in order to create oracle for Grover algorithm. I have started the task with a light weight SPECK cipher (got both classical and quantum ...
- 223
3
votes
1
answer
167
views
Can there be an equivalent classical circuit for a quantum circuit?
It is known that any classical circuit or algorithm can be implemented on a quantum computer using universal quantum gates. My question is, can there be a circuit with classical statistics which are ...
- 2,182
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 ...
- 2,182
2
votes
1
answer
165
views
What are the practical advantages of quantum GANs with respect to classical ones?
I read some papers on Quantum GANs, for instance this one and this one. I also noticed all the main quantum computing frameworks have a tutorial on quantum GANs, e.g. qiskit.
However I don't really ...
glS♦
- 21.7k
0
votes
1
answer
20
views
Why does having two classical registers sometimes only yeild one bit?
I was running some qiskit code on qasm_simulator to test something and I realized that, when I have two separate classical registers, sometimes only one bit is generated, and I'm trying to understand ...
- 7,494
1
vote
1
answer
189
views
How does Fujitsu's digital annealer work?
I have read Fujitsu's white paper for a brief introduction to their device:
http://marketing.us.fujitsu.com/rs/407-MTR-501/images/quantum-inspired-computing.pdf
As far as I know, Fujitsu's hardware is ...
- 9,346
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, ...
glS♦
- 21.7k
0
votes
0
answers
19
views
determine degree of boolean polynomial given as black box
I searched a lot but couldn't find a good resource that addresses this question. Given a boolean polynomial with $n$ boolean variables as a black box, what is the most efficient way to compute its ...
3
votes
2
answers
162
views
Are qubits just analog, continuous classical bits? [duplicate]
Topologically, classical bits (cbits) are essentially special cases of qubits restricted to the poles of the Bloch sphere. However, this restriction doesn't seem to be classical per se, but is simply ...
- 113
7
votes
1
answer
187
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 ...
- 52.3k
2
votes
0
answers
23
views
Best classical algorithm for period finding on finite Abelian groups
Given a finite Abelian group $G = \prod_{j=1}^n \mathbb{Z}_{m_j}$ with $m_j \geq 2$ and a function $h: G \to \mathbb{C}$ that is $s$-periodic. I have already proven that for all $\xi \in G$ we have $\...
- 21
1
vote
1
answer
209
views
Would the interest in building quantum computers decrease if a classical algorithm for factoring all integers in polynomial time is discovered?
Quoting Wikipedia:
No algorithm has been published that can factor all integers in polynomial time, that is, that can factor a $b$-bit number $n$ in time $O(b^k)$ for some constant $k$. Neither the ...
- 916
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 ...
glS♦
- 21.7k
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 ...
- 1,274
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 ...
1
vote
0
answers
40
views
Can a Hankel matrix $H$ be efficiently decomposed into a linear combination of unitaries (LCU), so that $H=\sum_k a_k U_k$
Suppose I have a Hankel matrix of arbitrary size $N\times M=2^n\times 2^m$ for integers $n<m$ (the qubit numbers of two circuits I have at my possession), given by:
$H=\begin{pmatrix}x_1&x_2&...
- 89
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 ...
- 12.8k
5
votes
1
answer
196
views
Has the possibility of there being a classical cryptography algorithm able to withstand quantum computing been proven?
Has it been proven, that a classical codec (encoder-decoder) (classical meaning one that doesn't require a quantum system for its operation) is possible, such that a quantum computer cannot crack it?
...
- 4,636
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 ...
glS♦
- 21.7k
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' ...
4
votes
2
answers
99
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 ...
- 31
4
votes
2
answers
853
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 ...
- 27
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?
- 452
3
votes
1
answer
130
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 ...
glS♦
- 21.7k
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 ...
- 19.3k
2
votes
2
answers
415
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 ...
glS♦
- 21.7k
1
vote
0
answers
70
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?
- 137
1
vote
1
answer
86
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 ...
- 2,695
1
vote
1
answer
82
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,...
- 2,695
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 ...
- 2,919
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 ...
- 30.2k
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 ...
glS♦
- 21.7k
4
votes
2
answers
145
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 ...
- 1,385
2
votes
0
answers
148
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 ...
- 159