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
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
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
9
votes
1
answer
3k
views
Creating bigger controlled nots from single qubit, Toffoli, and CNOT gates, without workspace
Exercise 4.29 from Quantum Computation and Quantum Information by Nielsen and Chuang has me stumped.
Find a circuit containing $O(n^2)$ Toffoli, CNOT and single qubit gates which implements a $C^n(...
- 5,772
1
vote
0
answers
54
views
Quantum multi valued decision diagrams
I recently came across the paper "QMDD: A Decision Diagram Structure for Reversible and Quantum Circuits" by Thornton and Miller. It deals with a way of compactly representing transformation matrix ...
8
votes
2
answers
679
views
Can a quantum computer (theoretically) do things a classical computer (literally) can't? [duplicate]
I've been searching the net for an answer to this question, but it's guetting quite confusing.
I want to know if there are some undecidable problems for a classical computer that a quantum computer ...
Val
4
votes
1
answer
207
views
Is $BQP$ in $P^{NP}$?
I read in the introduction of this paper
http://www.scottaaronson.com/papers/uncompute.pdf
that there is a problem $B$ such that $BQP^B \not\subset P^{NP^B}$, and that $B$ is in $BPP$. But, using ...
- 143
2
votes
1
answer
241
views
Quantum state probabilities and amplitudes - absolute value squared?
It has just appeared to me that I've overlooked a possibly important fact. When we want to calculate probability $p_x$ of measuring the state $X$ and we know the amplitude of $X$ is $\alpha$, we know ...
- 934
1
vote
2
answers
854
views
Multi-qubit gates matrix representation
Consider the gate used in Simon's Algorithm. It operates on a control register and target register, changing state like: $|\textbf{x}\rangle|\textbf{y}\rangle->|\textbf{x}\rangle|\textbf{y}\oplus f(...
- 934
7
votes
1
answer
379
views
What happens to multi-qubit quantum state after one of qubits is measured?
If we have a quantum state consisting of (let's say) 3 entangled qubits and we read the value of one of them, what happens to the probabilities of the remaining possible states?
For example, if we ...
- 934
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
5
votes
1
answer
337
views
Trying to understand how the first Hadamard gate in Deutsch–Jozsa algorithm works
I'm still a beginner in the quantum aspect of computer science (self-studying). So please bear with me if this may sound like a stupid question.
I know Hadamard gate transforms qubit into a ...
3
votes
1
answer
437
views
Measure two qubits, one from entangled pair, in Bell basis?
In quantum teleportation we require both sender (Alice) and receiver (Bob) to share an entangled pair of qubits in the $|\beta_{00}\rangle$ Bell state. Then, if Alice wants to teleport a quibt $|v\...
- 934
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
3
votes
1
answer
592
views
Why $\theta/2$ in common qubit representation?
If we take angle names as shown on the Bloch sphere below and a typical qubit representation written as $\cos(\theta/2)|0\rangle + \mathrm{e}^{-\mathrm{i}\phi}\sin(\theta/2)|1\rangle$, why do we ...
- 934
1
vote
1
answer
218
views
Can a CS grad student work on quantum field theory and string theory problems? [closed]
The mathematical aspect of particle physics theory are interesting and there seems to be a lot more connections being made to computation and information (like with complexity theory having some ...
- 119
0
votes
1
answer
598
views
A Black Box Algorithm
I'm taking an introductory quantum computations class and I am attempting to solve the following question(s), but we haven't touched on black box algorithms like this in class, and I honestly don't ...
- 13
16
votes
5
answers
20k
views
Will the future quantum computers use the binary, ternary or quaternary numeral system?
Our current computers use bits, so they use the binary numeral system. But I heard that the future quantum computers will use qubits instead of simple bits.
Since in the word "qubit" there is the ...
- 171
5
votes
2
answers
170
views
Are there specific rules for programming languages applicable to Quantum Computers?
What would be the requirements for programming languages that are used for quantum computers? Do standard procedural languages with their constructs be sufficient, and succinctly capture the computing ...
- 261
3
votes
1
answer
146
views
What difference does it make when universal classical gates in quantum computation are reversible but not unitary?
As I've come across Grovers algorithm I dont understand why when computing F(X), which is an oracle function people use classical reversible circuits(toffoli, fredkin) to evaluate the circuit. Why can'...
- 31
4
votes
2
answers
174
views
What happens to quantum algorithms such as BB84 if P=NP
Under the hypothesis that P=NP, many cryptographic protocols are no longer secure (i.e. attacks are feasible).
The BB84 algorithm is based on the idea that by observing a quantum state, one has to (...
- 1,594
16
votes
1
answer
911
views
Quantum Computing - Relationship between Hamiltonian and Unitary model
When developing algorithms in quantum computing, I've noticed that there are two primary models in which this is done. Some algorithms - such as for the Hamiltonian NAND tree problem (Farhi, Goldstone,...
- 1,103
0
votes
1
answer
112
views
Finding the private key in BB84 quantum cryptography
I'm trying to teach myself Quantum Cryptography for an exam I have soon, and I came across the following question:
To establish a common key, Alice and Bob analyse a sequence of 20 photon pairs. ...
- 149
1
vote
0
answers
92
views
Grover algorithm for known number of solutions
I am reading Computational Complexity book and specifically Grovers search algorithm. I am aware that if we knew in advance exact number of solutions $K$, then the basic algorithm can be tweaked to ...
- 1,614
2
votes
1
answer
227
views
Is Simon's problem a good NP-intermediate candidate?
We know that $BPP \subseteq BQP$ but we have no proof $BPP \subset BQP$
(Though we have the proof that BQP $!=$ BPP with an oracle)
Since Simon's problem (as factoring) it's easily solvable by a ...
- 227
3
votes
1
answer
353
views
Quantum algorithms and quantum computation
Is my (very high-level) understanding correct here regarding quantum algorithms —
Quantum computers can process a massive amount of operations in parallel to the nature of qubits and their ...
- 137
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
18
votes
5
answers
7k
views
Is Quantum Computer analog?
We used to have analog computers several decades ago. Modern days computers are Digital. What about Quantum computers? Is it analog or digital? I am asking this since qubit can be many things at the ...
- 1,759
2
votes
2
answers
267
views
What languages does a (1-way) quantum finite state automata recognize?
Sorry if this is well known, but most of the research is paywalled.
So far I know that it is a subset of the regular languages, but I cannot seem to find any (available) research which pins it down.
...
- 376
1
vote
1
answer
450
views
Qubits Related to RAM?
I read in this article that the amount of bits that can be emulated by a certain number of qubits is 2^(number of qubits). This is because each qubit can be in one of 2 states after it collapses, and ...
- 113
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
3
votes
2
answers
385
views
Quantum computer code cracking
everyone! I don't know a whole lot about the fields of encryption or quantum computing, but I've read a lot of articles on the subjects and that is prescisley what caused this question. I've been a ...
TheJ
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
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
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
5
votes
2
answers
2k
views
How does Grover's Quantum Sorting avoid reading the list?
It is well known now that Grover's quantum algorithm can SORT a database of $N$ entries in $O(\sqrt{N})$ time. How can an algorithm work without reading through the list of entries which needs $O(N)$ ...
- 2,844
1
vote
0
answers
123
views
Quantum Algorithms and CT vs Classical counterparts
How is Quantum Algorithms and Complexity Theory essentially different from Classical Counterparts?
Also how are non-deterministic Turing Machines(NTM) different from Quantum Turing Machines(QTM)? More ...
- 1,676
9
votes
3
answers
3k
views
What is meant by an oracle separation between classes $\mathsf{BPP}$ and $\mathsf{BQP}$?
In these notes about quantum computation by Scott Aronson, he explains that the computation classes $\mathsf{BPP}$ is contained in $\mathsf{BQP}$, but that they are not equal, and
So, the bottom ...
- 209
5
votes
2
answers
1k
views
Finding all marked elements using Grover's algorithm
Grover's algorithm uses an oracle function $f(x) \to \{0,1\}$ to find the location of a single marked element from an unordered database of $2^n$ elements with high probability. As part of an ...
- 181
10
votes
0
answers
175
views
(Slightly) faster simulation of quantum Fourier transform
Suppose I want to write a classical software simulator of a quantum circuit with $N$ qubits. When it comes time to simulate the quantum Fourier transform I can evaluate all $2^N$ states to determine ...
- 17.5k
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
724
views
Quantum computing roadmap
I have to create a roadmap for the quantum computing technology. Looking around I found the timeline on wikipedia that is pretty wide but does not highlight the key events in quantum computing ...
- 161
3
votes
4
answers
3k
views
The difference between a bit and a Qubit
Ok, I have done a lot of research on Quantum computers. I understand that they are possibly the future of computers and may be commonplace in approximately 30-50 years time.
I know that a Binary is ...
- 133
6
votes
4
answers
2k
views
The physical implementation of quantum annealing algorithm
From that question about differences between Quantum annealing and simulated annealing, we found (in commets to answer) that physical implementation of quantum annealing is exists (D-Wave quantum ...
- 113
8
votes
3
answers
2k
views
What is the relation between P vs. NP and Nature's ability to solve NP problems efficiently?
I was thinking about how nature can efficiently compute ridiculous (i.e. NP) problems with ease. For example, a quantum system requires a $2^n$ element vector to represent the state, where $n$ is just ...
anon
4
votes
1
answer
504
views
Controlled NOT gate a type of measurement?
I'm trying to understand the theory of quantum computing, and I'm a bit confused on a particular circuit:
Would the controlled NOT gate be a type of measurement, causing Q1 to be either |0> or |1>, ...
- 43
6
votes
1
answer
186
views
Origin of quantum complexity theory
Who was/were the first person/people to introduce the topic of quantum complexity theory and problem classes like BQP and QMA?
- 357
3
votes
2
answers
869
views
Quantum computing 'amplitudes'
As far as I understand, you receive an output from a quantum computer for an algorithm in the form of an amplitude, which is one of the many states your qubits may be in, however this amplitude is a ...
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
5
votes
1
answer
147
views
Help need to learn Quantum Computation and Information
I want to learn quantum computation and information. I am studying from Nielsen & Chuang book for this.
Is there any online vedio (lecture series) starts from
basics of quantum computation and ...
- 195
4
votes
1
answer
336
views
Tensor Product in Quantum Computation
I can not understand the following equality $$\langle ij|(|0\rangle \langle 0|\otimes I)kl \rangle= \langle i|0\rangle \langle 0|k \rangle \langle j|I|l \rangle?$$
Also to estimate phase $\phi$ in ...
- 195