Questions tagged [classical-computing]
For questions about the relation of Quantum Computing and Classical Computing, such as their relative performance.
6
votes
2answers
117 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 ...
6
votes
2answers
103 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 ...
3
votes
1answer
51 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 ...
8
votes
2answers
152 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;...
7
votes
1answer
61 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 ...
6
votes
3answers
141 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 ...
8
votes
3answers
245 views
Simplest algorithm for intuitively demonstrating 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 ...
6
votes
2answers
114 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 ...
12
votes
4answers
344 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' ...
16
votes
6answers
552 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 ...
7
votes
1answer
98 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.
118
votes
14answers
26k 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 ...
6
votes
3answers
175 views
Are we certain that quantum computers 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?
6
votes
3answers
143 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 ...
16
votes
2answers
2k 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 ...
30
votes
6answers
6k 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 actually execute it in practice? Is ...
14
votes
2answers
197 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 ...
22
votes
4answers
3k 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?
6
votes
3answers
112 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 ...
6
votes
0answers
83 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 ...
6
votes
1answer
49 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 ...
14
votes
2answers
473 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 ...
6
votes
1answer
93 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 ...
2
votes
1answer
83 views
What impact would have introducing the quantum switch effect in classical computing?
This divulgation article by Prof. Brukner talks about the possibility of creating a situation where
"A causing B" and "B causing A" which we call a quantum switch. Such a setup is similar to some ...
6
votes
2answers
272 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 ...
11
votes
1answer
68 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 ...
13
votes
3answers
410 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 ...
34
votes
2answers
2k 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'....
0
votes
1answer
262 views
How much memory is required to simulate a 48-qubit circuit?
This CDMTCS Report 514, 2017 entitled "The Road to Quantum Computational Supremacy" states (in Section 6) that the amount of memory needed to simulate random quantum circuits on classical computers ...
