The quantum computing tag is relevant for computing that uses quantum states such as superposition and/or entanglement to locate low energy states as solutions to complex problems (rather than laboriously enumerating and checking solutions as would be done with non-quantum traditional computing).
Questions tagged [quantum-computer]
889 questions
190
votes
5 answers
Why is Google's quantum supremacy experiment impressive?
In the Nature paper published by Google, they say,
To demonstrate quantum supremacy, we compare our quantum processor against state-of-the-art classical computers in the task of sampling the output of a pseudo-random quantum circuit. Random…
Bridgeburners
- 2,046
21
votes
1 answer
How Does a Quantum Computer Work?
I've read Wikipedia, I've read How Stuff Works, I've read The Singularity is Near, but I still just don't get it. How does a Quantum Computer work? It sounds very intriguing, but I just can't wrap my mind around it. I would greatly appreciate it if…
Andrew Garrison
- 433
17
votes
3 answers
Can a parallel computer simulate a quantum computer? Is BQP inside NP?
If you have an infinite memory infinite processor number classical computer, and you can fork arbitrarily many threads to solve a problem, you have what is called a "nondeterministic" machine. This name is misleading, since it isn't probabilistic or…
9
votes
6 answers
Why do some physicists believe that scalable quantum computing is possible?
If you drop a glass cup on the ground, it will break and shatter into pieces. This happens all the time and is consistent with quantum mechanics. But it never happens that a shattered glass cup rearranges itself from the ground into someone's hand…
Craig Feinstein
- 980
8
votes
2 answers
What nonstandard theory forbids quantum computers?
What would a nonstandard model which reproduces all experimental quantum data so far but still cause quantum computers to fail when implementing Shor's algorithm look like? Would it have to be very convoluted and conspiratorial, or are there natural…
7
votes
7 answers
Quantum computers: are they possible or impossible?
I know quantum computers are very complicated and my question is is there any way in "Principle" to create one? Are there already quantum computers being created?
jake
- 175
7
votes
1 answer
If quantum mechanics is ultimately deterministic, would Shor's factorization algorithm still work for large integers?
Victor Stenger argues that the apparent randomness in quantum mechanics is a result of the randomness in the macroscopic detectors (similar to the randomness in the laws of thermodynamics) and is not something that is inherent to quantum mechanics…
Craig Feinstein
- 980
7
votes
1 answer
Correspondence principle and quantum computers
I just read this article at https://medium.com/the-physics-arxiv-blog/7ef5eea6fd7a about the work of a physicist called Bolotin, that states that P!=NP (from computer science) implies that large quantum mechanical objects are not possible.
The…
user1817949
- 73
7
votes
3 answers
If quantum computing requires hundreds of digits of accuracy, how will it be possible?
Leonid Levin said, "Exponential summations used in QC require hundreds if not millions of decimal places accuracy. I wonder who would expect any physical theory to make sense in this realm." See…
Craig Feinstein
- 980
6
votes
2 answers
What is the most natural classical polynomial complexity class that includes all of BQP and NP?
Since we know that there are some oracle problems which can be solved on a quantum computer, but not on an NP machine with the same oracle, the idea of nondeterministic (i.e. infinitely parallel) machine is not sufficient to describe what is going…
5
votes
1 answer
Scaling of quantum error correction
I'm having a question regarding quantum error correction.
Using a large number of imperfect (but already very good) quantum gates, it is in theory possible to build an equivalent, error-corrected gate. What I don't understand, however, is how it…
Oli
- 607
5
votes
1 answer
How can a quantum dot be used as a qubit?
Many people say that quantum dot is a potential physical representation of qubit. A qubit should have two distinguishable states which may carry quantum information. What are the two states of a quantum dot which could be regarded as the two states…
Michael
- 51
4
votes
0 answers
Studying Feynman articles nowadays
I'm curious to know if it's useful to study Feynman article "Quantum Mechanical Computer" nowadays.
I'm a computer scientist, and i don't know any of the literature in quantum computers. Since long time has passed from 1985 it's a waste of time…
asdf
- 329
4
votes
1 answer
No cloning theorem and exclusive-or (XOR) operator
According to IBM's website,
[...]where we would [classically] have done an assignment (x=y), we instead initialize the target (x=0) and use exclusive or (x^=y).
This sounds like x is a copy (clone) of y, however cloning is impossible in quantum…
Kevin Kostlan
- 6,463
4
votes
1 answer
Continued Fraction Algorithm in Shor's Algorithm
I am just trying to make the final link of Shor's algorithm clear. Here $r$ is the order of $x$ modulo $N$.
We have a number $\psi$, which for a rational number $\dfrac{s}{r}$ satisfies
\begin{equation}
\Big| \dfrac{s}{r} - \psi \Big| \leq…
Zach Dean
- 93