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.
257
questions
14
votes
2
answers
8k
views
Intuition behind the Hadamard gate
I'm trying to teach myself about quantum computing, and I have a decent-ish understanding of linear algebra.
I got through the NOT gate, which wasn't too bad, but then I got to the Hadamard gate. ...
- 364
0
votes
1
answer
283
views
Does the fact that there exists a polynomial time quantum algorithm for integer factorization suggest that integer factorization is in P?
Just as the title says: Does the fact that there exists a polynomial time quantum algorithm for integer factorization suggest that integer factorization is in P? Additionally, if one could show that a ...
- 101
0
votes
1
answer
123
views
A question on the power of the operator in Grover's quantum algoritm
I'm new to quantum computing, so while studying Grover's algorithm I (and, I think a lot of other people too) could not help but notice that exactly the same operator is applied $\sqrt{N}$ times:
$$U ...
- 103
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
3
votes
0
answers
112
views
Quantum circuits for multiply-accumulation
Classically, multiplication can be done in $O(n \ \lg(n) \ 8^{\lg^* n})$ steps on a multi-tape Turing machine via Fürer's algorithm. Using that algorithm, combined with uncomputing, you can make a ...
- 5,772
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
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
1
vote
3
answers
212
views
Quantum CNot algorithm problem
I have a very simple quantum algorithm:
Let's start with two qubits in the state $|00\rangle$. I apply a Hadamard gate to the first one. Then I apply a CNot gate, with the first one as a control. ...
- 13
4
votes
0
answers
72
views
Cloning the output of a quantum program with unknown input but known measurements
Suppose Alice asks to use Eve's quantum computer. Alice loads her hidden quantum state into the computer, then gives Eve a program to run. The program will apply unitary operations and measurements to ...
- 5,772
4
votes
2
answers
456
views
Are there any useful deterministic quantum algorithms for decision problems?
The vast majority of known interesting quantum algorithms are probabilistic. The only deterministic quantum algorithms that I know of (which aren't trivially equivalent to a classical algorithm) are (...
- 984
7
votes
1
answer
989
views
Known problems in BQP \ NP?
The introduction to Nielsen and Chuang has an Euler diagram of the suspected relationships between various complexity classes which shows $\text{BQP}$ extending slightly outside of $\text{NP}$. Is $\...
- 984
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
5
votes
1
answer
2k
views
Computing Von Neumann Entropy Efficiently
The Von Neumann entropy $S$ of a density matrix $\rho$ is defined to be $S(\rho)= -\text{tr}(\rho \lg \rho)$. Equivalently, $S$ is the classical entropy of the eigenvalues $\lambda_k$ treated as ...
- 5,772
1
vote
1
answer
267
views
How correct was Justin Trudeau's explanation of Quantum Computing? [closed]
Recently, Canada's Prime Minister - Justin Trudeau - gave an impromptu explanation of Quantum Computing, much to the crowd's astonishment. I certainly thought that I "got" Quantum Computing a little ...
- 113
2
votes
2
answers
475
views
Why does 9 qubit Shor code have distance 3?
Distance of a Stabilizer code($S$) is defined by minimum weight of an element in $N(S)-S$ .
Why 9 qubit Shor code has distance 3?
Is there a way to directly see $N(S)-S$ from $S$?
- 139
1
vote
1
answer
168
views
How does equality works for qubit-vectors?
A bitvector of length N has 2^N different values. How many different values has a quantum bit vector of length ...
- 4,037
2
votes
1
answer
126
views
Quantum computer simulators with proper measurements
I have been looking for quantum computer simulators and came across QCAD (http://qcad.osdn.jp/). It is stated on their website that "Measurement gates on QCAD are different from real measurements."
...
3
votes
1
answer
209
views
CNOT, Hadamard and Φ quantum gates
How can somebody use these gates to create other gates like pauli's or other gates? Also how can somebody go from pauli's to CNOT, Hadamard and Φ quantum gates?
- 31
1
vote
1
answer
71
views
Computing a partial density matrix from an amplitude vector
Suppose you're given the list of $2^{2n}$ complex coefficients defining the state of a $2n$ qubit register. You want to compute the $2^n \times 2^n$ density matrix of the first $n$ qubits.
Is it ...
- 5,772
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
0
votes
1
answer
196
views
How many operations to produce this superposition of 3 qubits?
Suppose I have three qubits that of course represent $2^3=8$ states. I want to put these qubits so that they are in the particular superposition say...
$$a|000\rangle + b|001\rangle + c|010\rangle + ...
- 471
1
vote
2
answers
295
views
Constructing the matrix of a controlled quantum operation
How do we construct a matrix that takes into account whether the first qubit is set?
I am trying to construct the controlled-V matrix, but there is no quantum computational paper that describes it so ...
- 71
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
1
vote
1
answer
118
views
Are qubits written in a big-endian or little-endian order when grouped?
Say for instance you layout a quantum simulator like follows:
amps = [0] * 8 # 3 qubits
Therefore you are left with the following in binary:
...
- 71
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
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
1
vote
0
answers
46
views
2 qubits, correct way CNOT a 3rd qubit with the 1st? [duplicate]
Suppose I have 2 qubits in the state a|00>+b|01>+c|10>+d|11>. And suppose I want to perform some operation between only the 1st qubit and a 3rd qubit - for example a CNOT operation. What would be ...
- 471
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
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
3
votes
2
answers
221
views
Looking for interesting unanswered questions within complexity theory for a project [closed]
I'm looking for interesting open questions in complexity theory that someone with an undergraduate degree in math and comp/sci could theoretically tackle. I have strong interest in the polynomial ...
- 55
3
votes
3
answers
1k
views
Is it possible to entangle more than 2 qubits? If so, is it useful?
With 2 qubits, there are 4 ways to entangle the qubits - the four maximally entangled two-qubit Bell states, of which one is $1/\sqrt{2}(|00\rangle + |11\rangle)$.
Is it possible to entangle more ...
- 1,318
2
votes
1
answer
387
views
Why does the Toffoli gate output c XOR (a AND b) instead of just a AND b?
The Toffoli gate takes in three inputs and gives out three outputs, and is often referred to as the quantum AND gate.
It takes in a,b,c and gives out a, b, c XOR (a AND b).
Why does it do that, ...
- 1,318
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
0
answers
28
views
How are quantum computers able to process certain tasks faster than regular computers? [duplicate]
I've read posts everywhere and watched videos but still I don't understand one part of it. How are they able to process all these operations in parallel.
So based on the landscape example here.
How ...
- 31
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
6
votes
1
answer
618
views
Does a Hadamard Gate have uses outside of pure and evenly mixed states?
The standard usage cases for the Hadamard gate seem to be passing a pure $|0\rangle$ or $|1\rangle$ state in to get an even amplitude (probability) mixed state which has either matching or mismatching ...
- 1,318
-1
votes
1
answer
169
views
How do Quantum Computers destructively interfere the wrong answer? [duplicate]
From various sources (one being this), I've heard that quantum computers find the correct answer in a sea of possible ones by destructively interfering the wrong ones with each other, and the right ...
- 323
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
1
vote
1
answer
157
views
Where does entanglement fit into quantum computing?
I've been reading up on quantum computing online from various sources, including this link http://twistedoakstudios.com/blog/Post2644_grovers-quantum-search-algorithm.
I get how quantum gates work, ...
- 1,318
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
2
votes
2
answers
378
views
Can quantum computer become perfect chess player?
Can quantum computer become perfect chess player?
Can it determine whether (when both players are perfect) win white or black? (or is it dead heat?)
- 413
0
votes
1
answer
146
views
Quantum computer memory size
Quantum computers are going to have enormous number of operations per second (in some situations exponentially more than classic computers).
Does it also hold for memory size? Are QC going to have ...
- 413
4
votes
0
answers
221
views
If BQP is contained in any level of the Polynomial Hierarchy, does it then follow that $NP \subseteq BQP$ implies $PH \subseteq BQP$?
I think this is implied in this paper by Aaronson (http://www.scottaaronson.com/papers/bqpph.pdf) but I am not sure.
Begin with $NP \subseteq BQP$ (*)
$\Sigma_{2}^{P} = NP^{NP} \subseteq BQP^{BQP} = ...
- 41
3
votes
1
answer
67
views
What can a quantum query to a function do?
The $n$-qubit Hadamard gate acts as,
$$H (\otimes^n \vert 0 \rangle ) = \otimes ^n ( H | 0 \rangle ) = \otimes ^n ( \frac { |0\rangle + |1\rangle }{\sqrt{2} } ) = \frac{1}{\sqrt{2^n} } \sum_{x \in \{ ...
- 1,105
18
votes
5
answers
7k
views
Why is a quantum computer not capable of solving more problems than a classical computer? [duplicate]
On the Wikipedia page for quantum algorithm I read that
[a]ll problems which can be solved on a quantum computer can be solved on a classical computer. In particular, problems which are undecidable ...
- 305
1
vote
0
answers
36
views
Will the growth of calculation speed of personal computer end after that of classical computer will end? [closed]
According to the answer of Andrew Yeats in this link, quantum computer's advantage is so narrow that personal computer is not likely to benefit from the development of quantum computer. I think this ...
2
votes
1
answer
98
views
Question about the Simon's algorithm
This comes from trying to understand the "Simon's algorithm".
So we have a set of $2^n$ kets $|x_i \rangle$ one each for $i \in \{0,1\}^n$. Each $x_j \in \{0,1\}^n$. And we have the further ...
- 1,105
3
votes
1
answer
255
views
How many inputs does the Hadamard gate have?
Look at the diagram in the middle of page 6-3 here,
http://stellar.mit.edu/S/course/6/fa14/6.845/courseMaterial/topics/topic3/lectureNotes/qctlec6/qctlec6.pdf
I am confused as to how should one think ...
- 1,105
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
1
answer
611
views
Evaluating Grover's algorithm on 3-SAT
I recently asked this very similar question on how Grovers algorithm must be modified in order to solve 3-SAT and learned that it actually needs no modification at all.
However, what I still don't ...
- 401