A computation model which relies on quantum-mechanic phenomena, such as entanglement and superposition. This generalizes the probabilistic model of computation.
36
votes
2answers
2k 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 ...
22
votes
2answers
642 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 ...
17
votes
3answers
3k views
Why and how is a quantum computer faster than a regular computer?
I'm currently reading a book (and alot of wikipedia) about quantum physics and I'm yet to understand how is a quantum computer can be faster than the computers we have today? what causes the ...
13
votes
1answer
228 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, ...
11
votes
5answers
4k views
Why is a quantum computer not capable of solving more problems than a classical computer?
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 ...
11
votes
1answer
1k 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 ...
11
votes
2answers
1k 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 ...
10
votes
2answers
281 views
Organisation and Architecture of Quantum Computers
What are devices and their interconnections used alongwith Quantum Processors? Are they compatible with hardware devices like Cache, RAM, Disks of current computers?
10
votes
2answers
2k 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?
10
votes
2answers
2k 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 ...
10
votes
1answer
177 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 ...
8
votes
3answers
288 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?
8
votes
2answers
612 views
What is the difference between classical crypto and post-quantum crypto?
Will there be a need to change the definitions of security if we have quantum computers? What cryptographic constructions will break? Do you know a survey or an article that explains what will be ...
7
votes
2answers
433 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 ...
6
votes
4answers
708 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 ...
6
votes
0answers
99 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 ...
5
votes
3answers
737 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 ...
5
votes
2answers
216 views
Can a quantum computer (theoretically) do things a classical computer (literally) can't?
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 ...
5
votes
1answer
111 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?
5
votes
1answer
275 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 ...
5
votes
2answers
264 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 ...
5
votes
1answer
109 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 ...
5
votes
2answers
671 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 ...
4
votes
2answers
308 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 ...
4
votes
2answers
466 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 ...
4
votes
1answer
56 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 ...
4
votes
1answer
82 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 ...
4
votes
2answers
284 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)$ ...
4
votes
2answers
159 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 ...
4
votes
1answer
77 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 ...
4
votes
1answer
95 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 ...
3
votes
1answer
376 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 ...
3
votes
1answer
110 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 ...
3
votes
2answers
69 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 ...
3
votes
4answers
870 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 ...
3
votes
1answer
26 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 ...
3
votes
1answer
37 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 ...
3
votes
1answer
90 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>, ...
3
votes
2answers
143 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 ...
3
votes
1answer
68 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 ...
3
votes
1answer
41 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 ...
3
votes
1answer
84 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 (http://en.wikipedia.org/wiki/BB84) is based on the idea that by ...
3
votes
2answers
149 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 ...
3
votes
1answer
21 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 ...
2
votes
2answers
434 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 ...
2
votes
3answers
87 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 ...
2
votes
2answers
253 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 ...
2
votes
1answer
189 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 ...
2
votes
2answers
117 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.
...
2
votes
1answer
49 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 ...
