Questions tagged [quantum-computing]
A computation model which relies on quantum-mechanic phenomena, such as entanglement and superposition. This generalizes the probabilistic model of computation.
39
questions
43
votes
6
answers
26k
views
Why and how is a quantum computer faster than a regular computer?
I'm currently reading a book (and a lot of wikipedia) about quantum physics and I've yet to understand how a quantum computer can be faster than the computers we have today.
How can a quantum ...
- 657
11
votes
3
answers
942
views
References on comparison between quantum computers and Turing machines
I was told that quantum computers are not computationally more powerful than Turing machines.
Could someone kindly help in giving some literature references explaining that fact?
- 171
53
votes
2
answers
7k
views
How to define quantum Turing machines?
In quantum computation, what is the equivalent model of a Turing machine?
It is quite clear to me how quantum circuits can be constructed out of quantum gates, but how can we define a quantum Turing ...
- 20.5k
21
votes
2
answers
7k
views
Universality of the Toffoli gate
Regarding the quantum Toffoli gate:
is it classicaly universal, and if so, why?
is it quantumly universal, and why?
- 20.5k
3
votes
3
answers
2k
views
How do quantum computers find the global minimum?
If I understand correctly, quantum computers work by trying multiple methods of solving a problem simultaneously, using quantum superposition. However, if you try to "look" at a superposition-ed atom, ...
- 323
33
votes
2
answers
11k
views
What is the difference between quantum TM and nondetermistic TM?
I was going through the discussion on the question How to define quantum Turing machines? and I feel that quantum TM and nondetermistic TM are one and the same. The answers to the other question do ...
- 533
9
votes
2
answers
2k
views
Applying a multi qubit quantum gate to specific qubits
A controlled not gate matrix looks like this:
$$\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
\end{bmatrix}$$
...
- 1,318
37
votes
2
answers
3k
views
Quantum lambda calculus
Classically, there are 3 popular ways to think about computation: Turing machine, circuits, and lambda-calculus (I use this as a catch all for most functional views). All 3 have been fruitful ways to ...
- 4,792
18
votes
3
answers
909
views
What specifically makes quantum computers useful?
I know that quantum computers are able to process a superposition of all possible states with a single pass through the logic.
That seems to be what people point to as being what makes quantum ...
- 1,318
9
votes
3
answers
3k
views
How to apply a 1-qubit gate to a single qubit from an entangled pair?
Reading about superdense coding I came upon a calculation I can not understand.
We have an EPR entangled pair of qubits $\frac{1}{\sqrt2}(|00\rangle + |11\rangle)$ and we want to apply a Pauli X gate ...
- 934
7
votes
2
answers
2k
views
Quantum computers, parallel computing and exponential time
I've read that quantum computers can solve 'certain problems' exponentially better than classical computers. As I think I understand it, it's NOT the same to say that quantum computers take any ...
- 693
4
votes
1
answer
347
views
Can you take classical code and compile it to quantum code?
Is there anyway for example, to take a trivial program from C such as:
int main() {
int i = 1 + 1;
return 0;
}
And compile this down to some form of Quantum ...
- 71
52
votes
3
answers
14k
views
Why did Google not use an NP problem for their quantum supremacy experiment?
Reading discussions of the recent quantum supremacy experiment by Google I noticed that a lot of time and effort (in the experiment itself, but also in the excellent blog posts by Scott Aaronson and ...
- 683
32
votes
5
answers
7k
views
Can Quantum Computing solve Problems not even a Turing Machine can solve? [duplicate]
In his book "The Fabric of Reality", Penguin Books 1998, p. 218, David Deutsch says that the first quantum computer (built 1989 in the office of Charles Bennet, IBM Reasearch) "became the first ...
ggreiter
30
votes
1
answer
8k
views
Quantum Computing and Turing Machines: Are Turing Machines still an Accurate Measure?
In class last week, my professor commented and said that Turing machines are used as a standard measure/model of what is computable and are a helpful basis of discussion for that subject. She also ...
- 682
19
votes
2
answers
6k
views
Could quantum computing eventually be used to make modern day hashing trivial to break?
Simply put, if one were to build a quantum computing device with the power of, say, 20 qubits, could such a computer be used to make any kind of modern hashing algorithm useless?
Would it even be ...
- 325
14
votes
2
answers
1k
views
Quantum Supremacy Task
I’m trying to understand the task performed by Google’s Sycamore that recently achieved alleged Quantum Supremacy. I’ve read the paper in Nature but the actual task that would have taken 10,000 years ...
- 241
14
votes
1
answer
2k
views
Is it proven that quantum computation is no better at solving NP complete problems than classical computation?
Is it proven that quantum computation is no better at solving NP complete problems than classical computation or it's just believed?
- 243
11
votes
1
answer
1k
views
What type of algorithms are faster with a quantum computer?
I am a beginning CS student and I am learning algorithms. I heard that even with quantum computers, that general sorting algorithms can never have better than $n\log n$ time. However, I also know that ...
- 213
11
votes
3
answers
2k
views
Is there any proof that quantum computers are more efficient than classical computers?
Shor's algorithm is often used as the argument. It can solve the factorization problem faster than any known algorithm for classical computers. Yet, we have no proof classical computers can't also ...
- 4,037
9
votes
2
answers
6k
views
Shor's Algorithm speed
I'm a fledgling computer science scholar, and I'm being asked to write a paper which involves integer factorization. As a result, I'm having to look into Shor's algorithm on quantum computers.
For ...
- 193
8
votes
1
answer
260
views
Are there any problems that require exponential time in quantum computing?
Given the fact that the qbits have superpositions, and have more representational power compared to circuits, are there any problems that require at least exponential time to guarantee a solution with ...
- 1,425
6
votes
2
answers
1k
views
Quantum computers and computable functions
A quantum computer can possibly calcluate computable functions faster, but it can't calculate functions which a normal computer can't calculate?
If a function is not computable? Does this mean it ...
- 290
4
votes
2
answers
4k
views
How is the oracle function for Grover's Search algorithm obtained?
I've been using the IBM quantum experience to learn about and simulate Grover's algorithm. When they create the algorithm, they use a different set of gates depending on which oracle function $f(x)$ ...
user53686
4
votes
1
answer
222
views
Can current quantum computers decide languages that Turing Machines cannot?
I am currently learning Computing Theory at university, and we were on the topic of Turing-Decidability, Recognizability, etc. Showing that a problem is undecidable with Turing machines due to ...
- 519
4
votes
1
answer
209
views
Does entangling 100 qubits require a 2^100 X 2^100 Hadamard gate?
Suppose I have 100 qubits that I want to entangle and put into superposition. To do so I construct a Hadamard gate to do this. By definition, the Hadamard is going to be a 2^100 X 2^100 matrix - which ...
- 471
4
votes
2
answers
146
views
Should we always think of problems higher in the polynomial hierarchy as harder than problems lower in the hierarchy?
This "research vignette" (whatever that is) claims that the polynomial hierarchy
classifies problems according to a natural notion of logical complexity, and is defined with an infinite number of ...
- 984
3
votes
2
answers
296
views
How must Grovers algorithm be modified in order to solve 3-SAT?
Grover's algorithm was designed for a database with exactly one item that matches a given search criterion, and can be used to find that very item.
However, when checking whether a given formula is ...
- 401
3
votes
2
answers
5k
views
Hadamard gate on entangled qubit
TL;DR: If you have two entangled qubits in the state $|00\rangle + |11\rangle$, what is the result of applying the Hadamard gate on the second qubit, and why?
I am trying to understand $\text{PSPACE} ...
- 175
3
votes
1
answer
238
views
IS $LOGSPACE\subsetneq QMA$ an open problem?
Having read some chapters of Computational Complexity: A Modern Approach, I see no time or space hierarchy theorem which applies to this case. As far as I can see, we know the following inclusions:
$...
- 4,237
3
votes
2
answers
2k
views
Simple explanation of Simon's Problem
I just read the Wiki article for Simon's Problem but I don't fully understand it because I don't follow the symbolic notation used to describe functions (I am not a computer scientist).
Can someone ...
- 153
3
votes
0
answers
119
views
Will quantum computers out-scale classical computers at P-problems?
It is my understanding that quantum computers have gained interest, because some interesting problems are suspected to be in the BQP-class, but not in the P-class (integer factorization, ...). Quantum ...
- 31
3
votes
1
answer
259
views
How do you apply a multi qubit gate to specific qubits in a multi qubit circuit?
Let's say that you have a 6 qubit system and you want to apply a Hadamard gate to qubits 2 and 4.
How would you construct a matrix that did that, while leaving the state of the other qubits alone?
- 1,318
3
votes
1
answer
816
views
How to measure processing power of a quantum computer?
Is there any way to get an equivalent of computing power of quantum computers in terms of computing power of common computers? I mean, how many teraflops (or so) can a quantum computer compute? How ...
- 225
2
votes
3
answers
1k
views
How is quantum function $f(x) = a^x \mod N$ constructed in Shor's algorithm?
I can't see how I can apply quantum function $a^x\mod N$ to initial states. Explanations of Shor's algorithm often skips this part, and I do not see what unitary matrix this algorithm would correspond ...
- 21
2
votes
2
answers
304
views
Can hypercomputation compute all kinds of incomputable numbers/functions/problems…etc?
Hypercomputation is a "cheat" that extends the capability of a Turing machine or quantum computer or cellular automaton by adding extra abilities. A standard method is "Oracle machines", Turing ...
- 137
2
votes
2
answers
152
views
Must you work with all qubits in a circuit when applying a gate?
When looking at this question:
How to apply a 1-qubit gate to a single qubit from an entangled pair?
And other questions, it makes it seem like when you have a quantum circuit involving $N$ qubits, ...
- 1,318
1
vote
1
answer
84
views
Why does quantum cost on gates formed from specific qubit gates not factor swap gates into account?
I've been reading a number of quantum computation research papers that claim quantum cost's that do not add up.
For instance, in this paper - there is a claim that the MTSG gate is a quantum cost of ...
- 71
0
votes
1
answer
115
views
In the shor's quantum circuit, what is the transformation of the modular operating gates?
I know different parts of this circuit, just I have a problem with that part that I circled in picture.
I want to know the function of that part.
If you have useful information about it, please ...
- 1