# 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.

263 questions
Filter by
Sorted by
Tagged with
1 vote
36 views

### Representing classical circuits with quantum gates

Many problems in computer science input boolean circuits to problems. Just as a toy example, let's define the below problem to be called $A$: Given a polynomial depth circuit with $N$ bits of output, ...
130 views

### Uncomputing measurement gate?

So one of Aaronson's lecture note (https://www.scottaaronson.com/democritus/lec10.html) pointed out that, if we'd like to simulate a BQP-oracle, technically speaking, the oracle of address-target form....
473 views

### is $P_{CTC} = BPP_{path}$?

I think that these two classes should be the same, but I can't find any literature about this and have a limited background on the topic. This is my reasoning, and I would like to know if (1) this is ...
112 views

### How do two H gates act on two entangled qubits?

In this circuit, if the two qubits are initialized at state 0, then after the oracle they are entangled and in the state: $$\frac{1}{2} (|00\rangle+|01\rangle+|10\rangle-|11\rangle)$$ My question is, ...
91 views

### What happens if we change $\mathcal{BQP}$ to allow quantum bits, but not quantum gates?

In the definition of the class $\mathcal{BQP}$ found in textbooks we (as the circuit builders) have access to an unlimited number of deterministic zero-initialized qubits and to a finite set of ...
40 views

### Are Quantum algorithms probing the oracle?

Considering Deutsch–Jozsa algorithm problem statement, of not being able to recognize "constant functions" from "balanced functions" on single call conventionally is clear to me... ...
25 views

### Good book on (Quantum) Complexity and Computability Theories to start learning the theorem $MIP^* = RE$ as an operator algebraist

I am looking for some greatest references that could help me understand the theorem $MIP^* = RE$ ($MIP*=RE$) step by step. The paper (The Connes Embedding Problem: A guided tour) covers various ...
4k views

### What is the difference between quantum computing and parallel computing?

Quantum computing essentially relies on the fact that qubits maintain multiple possible states simultaneously. Parallel computing too processes multiple states simultaneously. So what is the ...
15k views

### Would the P vs. NP problem become trivial as a result of the development of universal quantum computers?

If someone were to build a universal quantum computer, would that have any implications on the problem of P vs. NP?
56 views

I've been working on Quantum Circuits for a 1.5 months. And firstly i've created Full Adder in Quantum Circuit. And first times i was creating Full Adder with too Qubits. But last week i created ...
52 views

1 vote
42 views

### Making statements about quantum complexity theory

It is my understanding, based on this question that problems solved on quantum computers with oracles don’t make any statements about BQP in relation to other complexity classes. The fallacy is in ...
2k views

### How $N$ qubits correspond to $2^N$ bits?

I read everywhere that $N$ qubits correspond to $2^N$ bits. Let's start with 1 qubit, which is commonly represented by $\alpha |0\rangle + \beta |1\rangle$ where alpha and beta are complex numbers. ...
60 views

### Does quantum computing imply LPO?

The binary expansion of a given real number can be encoded as an amplitude using the inverse QPE. Together with Amplitude Amplification, I wonder if this could indicate that the (some weakened?) ...
61 views

### Quantum Turing machine

Is there a formal definition of a 'Quantum Turing machine'? I am mainly interested in how the tape position would move. https://en.wikipedia.org/wiki/Turing_machine https://en.wikipedia.org/wiki/...
1 vote
68 views

### Is quantum computing a serious usable instrument for the IT industry?

Following this latest and very exciting research object I can't find till now a usable computer. By computer I understand a definitive switchable Hardware. I would like to call actual "quantum ...
73 views

### Why doesn't the Deutsch Jozsa algorithm on a classical computer show P != BPP?

I recently saw this answer on a question in the Quantum Computing SE. The answer demonstrated how we can probabilistically find the answer to the Deutsch Jozsa problem on a PTM in $O(1)$ time, with an ...
25 views

### Quantum algorithms speedup illustration

I know that to illustrate speed-up advantage of Grover's algorithm we can apply "square root": if the brute force search takes 100 hours, Grover's quantum search algorithm should take about ...
49 views

### Are there any probabilistic models of computation that can strongly simulate themselves?

I was reading this question over on the quantum computation stackexchange, and the top answer stated that you can't (strongly) simulate even a probabilistic turing machine, on itself. I was just ...
40 views

### are computer errors inevitable?

this is my First post,I apologize for my ignorance. The question is: Could a programmer (human or Ai) with all the computing power and infinite time create a simulation of a world with our same laws ...
1 vote
54 views

### What is different between two classes are 'incomparable' or two classes are 'not equal'?

Arora and Barak states (p. 230) the following: What is the relation between $BQP$ and $NP$? It seems that quantum computers only offer a quadratic speedup (using Grover’s search) on $NP$-complete ...
1 vote
78 views

### Can quantum computers be modelled as a classical computer with access to an oracle?

Quantum computers can solve certain problems faster than classical computers e.g factoring numbers. and this is because quantum computers can do a fourier transform on $n$ qubits in $O(n^2)$ time as ...
59 views

### SAT and #SAT in Quantum

Let us look at the two questions that are NP-complete for a classical computer: Given an arbitrary Boolean expression, find an assignment of variables that evaluates the expression to $0$ (SAT). ...
70 views

### Quantum Boolean SAT algorithm?

Is there a quantum SAT algorithm, a quantum analogue of the DPLL or CDCL algorithms? Note: I'm not looking for the quantum analogue of the Boolean satisfiability problem (though that would be ...
1 vote
86 views

### What would be the conseuqences of BQP = NEXPTIME?

On wikipedia it says that $BQP ⊆ EXP$. However it is not known if $BQP \subset EXP$ Also I've seen that $PSPACE$ could contain $NEXP$ and does contain $BQP$. For this were assuming the incredibly ...
1 vote
47 views

### Confusion about whats being processed in a quantum computer

Please correct me if im wrong but this is how I think quantum computers work. Say we have a q-bit. The q-bit is put through a quantum gate to put it into a superposition and manipulate its ...
94 views

### What is the computer science interpretation of a qubit?

I am a CS major trying to decipher quantum computing. I have done some elementary study on qubits and I always seem to get lost at the "infinitely many" states that the qubit can have. And I ...
167 views

### Is QMA known to contain Co-NP?

Is QMA known to contain Co-NP? If not, would Co-NP being contained in QMA have any implications for other complexity classes. (e.g. Causing the polynomial heirachy to collapse.)
310 views

### What is the fastest classical "period-finding" algorithm that can replace the Quantum Fourier Transform in Shor's algorithm?

Shor's algorithm uses the Quantum Fourier Transform to find the period the function a^x mod N with "a" being a constant integer less than N and N being a ...
62 views

### Is it possible to use a quantum computer simulation to perform a cyber attack?

Is it possible to use a quantum computer and or a simulation to perform a cyber attack on classic computers? This is part of a research objective I'm trying to figure out.
30k 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 ...
1 vote
44 views

### How do I search for Verification of Quantum Computing

So, in quantum computing, each qbit has a 50/50 chance of being in either the state of 1 or 0 when you measure it. Simple enough. But I've heard reports a while ago about some company having ...
1 vote
48 views

### What is the "formula" for "any cipher can be deciphered by a quantum computer"?

There are several quantum complexity classes in different ways analogous to NP: NQP, QMA, and, as I understand, others. P=NP BPP=NP in simple words means "any cipher can be deciphered by a ...
113 views

### Why is CNOT the only non-trivial reversible gate for two input bits?

The Wikipedia page on the Toffoli gate mentions that CNOT is the only non-trivial reversible gate on two input bits. The CNOT gate computes the following function:  00 \to 00 \\ 01 \to 01 \\ 10 \to ...
2k views

### Is it possible to construct a C^5(U) with V^2=U and no work qubits (Nielsen & Chuang Exercise 4.28)

My question is related to the exercise 4.28 in the book of Nielsen and Chuang (Quantum Computation and Quantum Information). Here is the exercise For $U=V^2$ with $V$ unitary, construct a $C^5(U)$ ...
1k views

### Could a quantum computer perform linear algebra faster than a classical computer?

Supposing we had a quantum computer with a sufficient number of qubits, could we use it to do linear algebra faster than we could with a classical computer? What sort of speedup could we expect? Has ...
152 views

### Is there a concept of probabilistic quantum computers?

Answering my question Yonatan N said a statement from which follows that there are computable functions of quantum time complexity strictly above polynomial. Accordingly a Quora answer Quantum ...
200 views

### How will Big O be with quantum computers?

I don't even know if this is the right place to ask this this...but how will Big O be with quantum computers? More specifically, will the worst case always be constant? If yes, how will this change ...
395 views

### Why are complex numbers needed to define qubits?

I have started learning about quantum computing, and I have been told that you can forget about the physics and think of qubits as a natural generalization of the notion of bit. According to this view,...