# Tagged Questions

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

33 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?)
38 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 ...
62 views

276 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 ...
323 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 ...
85 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 ...
72 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 ...
92 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 ...
38 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 ...
59 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 ...
128 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 ...
736 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 ...
83 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 ...
46 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 ...
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 ...
233 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, ...
43 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. ...
30 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 ...
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 ...
191 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 ...
188 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 ...
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 ...
279 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 ...
119 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. ...
45 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 ...
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 ...
153 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 ...
126 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 ...
262 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 ...
451 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 ...
291 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)$ ...
### 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 ...