A computation model which relies on quantum-mechanic phenomena, such as entanglement and superposition. This generalizes the probabilistic model of computation.

learn more… | top users | synonyms

1
vote
1answer
45 views

Will the future quantum computers use the binary (base 2), the ternary (base 3) or the quaternary (base 4) 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 ...
2
votes
0answers
48 views

Scalable quantum computation vs Uncertainty Principle [migrated]

What does it means for a Quantum Computer to be scalable? I see a zero sum game between Quantum physics measurement being unpredictable and Quantum computing being scalable (and classically ...
4
votes
0answers
51 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 ...
3
votes
1answer
24 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
60 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 ...
12
votes
1answer
154 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, ...
0
votes
1answer
24 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. ...
1
vote
0answers
22 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
vote
1answer
30 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 ...
1
vote
1answer
153 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 ...
1
vote
0answers
79 views

How to do Tensor product of two qubits using gates [closed]

I want to do tensor product of two qubits which are passed through two Hadamard gates. I understand feeding the control bit of CN gate the output of Hadamard gate and target bit |0> gives me the Bell ...
10
votes
1answer
893 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 ...
5
votes
2answers
118 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 ...
2
votes
2answers
83 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. ...
1
vote
1answer
36 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 ...
15
votes
3answers
2k 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 ...
3
votes
2answers
77 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 ...
2
votes
1answer
75 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 ...
2
votes
2answers
124 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 ...
1
vote
2answers
235 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 ...
4
votes
2answers
170 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)$ ...
0
votes
0answers
49 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)? ...
4
votes
2answers
302 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
2answers
114 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 ...
5
votes
0answers
75 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 ...
7
votes
2answers
293 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 ...
3
votes
1answer
260 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
4answers
405 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 ...
5
votes
4answers
500 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 ...
4
votes
3answers
407 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 ...
3
votes
1answer
75 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>, ...
5
votes
1answer
103 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?
3
votes
2answers
135 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 ...
7
votes
3answers
238 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?
5
votes
1answer
102 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 ...
3
votes
1answer
92 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 ...
10
votes
2answers
913 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
2answers
254 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?
7
votes
2answers
362 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 ...
19
votes
1answer
467 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 ...
10
votes
2answers
999 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 ...
9
votes
2answers
1k 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?
30
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 ...