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.

Filter by
Sorted by
Tagged with
2
votes
1answer
30 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 ...
0
votes
2answers
28 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$ bits in $O(n^2)$ time as ...
0
votes
1answer
26 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 ...
1
vote
1answer
34 views

What is the “formula” for “any chipher 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 ...
2
votes
1answer
40 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 ...
2
votes
2answers
47 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 ...
3
votes
1answer
95 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,...
1
vote
1answer
16 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, ...
2
votes
0answers
23 views

Special Properties for Oracles in HSP

Let $(G,+)$ be an abelian group, $X$ a finite set (of "colors"), and $f:G \to X$ a function such that there exists a subgroup $H<G$ for which $f$ separates cosets of $H$, i.e. $\forall a,...
0
votes
1answer
15 views

Relaxation possibilities of the lower bound worst case sorting algorithms without quantum computation

The sorting algorithms (merge-sort, quicksort...) are tought to have an absolutely hard lower bound which can not be outperformed by computation alone and this bound is $n*log_{2}(n)$, The reason for ...
1
vote
0answers
21 views

BPP and BQP: Optimization Versions?

For optimization problems, I found complexity classes analog to some classes for decision problems, e.g. PO and NPO, mirroring P and NP for decision problems in the sense that optimization problems in ...
0
votes
0answers
28 views

Isn't measuring the results the main bottleneck of quantum computers?

I have researched a bit about quantum computers, and hopefully understood that the main advantage does lie in the utilisation of superpositions in order to compute (manipulate qubits) in parallel ...
2
votes
0answers
26 views

Generalizing Quantum Computation

When you first learn more about computation you can imagine it in terms of boolean circuits. That is you get a boolean vector $v \in \lbrace 0,1\rbrace ^n$ which you can then apply a circuit $C$ to ...
4
votes
1answer
166 views

Can quantum computing help solve NP-Complete problems?

i was just wondering if quantum computing has done any good so far in solving NP complete problems. I am aware that quantum computing does solve some NP problems which are classically hard in ...
0
votes
3answers
250 views

What are analog and digital in computer science?

I once thought that any analog computer is any computer which "doesn't need electrical current to work". I once thought that any digital computer is any computer which "does indeed need ...
1
vote
0answers
19 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.)
5
votes
1answer
68 views

Factoring algorithms after number field sieves

It seems that the General Number Field Sieve (GNFS) became number one and then RSA stopped its factoring challenges and there have been no advances in factoring algorithms besides quantum computers. ...
1
vote
0answers
20 views

What is the simplest quantum algorithm to visualize a quantum computation?

I'm interested to visualize how a simple quantum computation can be done, step by step. Can you help me? I need any simple example of how qubits can be used to make a computation.
0
votes
0answers
24 views

Diagonalization in oracle separation between QMA and PP

Reposting from cstheorystackexchange for more visibility: Diagonalization is a very common technique to find oracle separations. For example, it can be used to separate $\cal{P}$ and $\cal{NP}$, ...
4
votes
0answers
174 views

Data structures for quantum computers

In classical computers we have List,Queue,Tree & etc data structures, since classical computers using 1's & 0's on those data structures. Then what happens when it comes to quantum computers, ...
3
votes
1answer
58 views

Is there a complexity class QPP?

The complexity class PP is not considered tractable, because the probability of success can get arbitrarily close to 50% from above as the problem instances get larger, so that (e.g. if this approach ...
1
vote
0answers
18 views

Why are MM-1QFA strictly more powerful than MO-1QFA?

While dealing with quantum finite automata (QFA), I repeatedly come across the statement that measure-many QFA (MM-1QFA, KW97) are strictly more powerful than measure-once QFA (MO-1QFA, MC97); both ...
1
vote
2answers
84 views

Can neural network process randomness?

So the question is : Is it theoretically possible to feed a neural network with some random values to expect an output since randomness is a lack of knowledge in most case. For this question, I've ...
2
votes
1answer
88 views

Can quantum computers really compute a vast number of possible solutions simultaneously?

This link says They are not constrained to stepwise calculations but, rather, can compute a vast number of possible solutions simultaneously—and at a speed that is far beyond anything we can ...
1
vote
1answer
67 views

Understanding the state vector in Quantum Computing

I have just started to learn QC. It is said that The quantum state of $N$ qubits can be expressed as a vector in a space of dimension $2^N$ If there is $1$ qubit then we have two possible state ...
2
votes
1answer
51 views

Understanding DIQKD protocol, a few questions

I'm refering to this paper here "Fully Device-Independent Quantum Key Distribution" (Umesh Vazirani and Thomas Vidick) and unfortunately there are many things I don't understand. 1) Page 3: by the ...
0
votes
0answers
15 views

NDFA has maximum states as 2^n the same for qubits in quantum computation.How they can be distinguished in means of computation? [duplicate]

I am a Computer Engineer. I studied basics of Quantum Computation. In dealing with multiple states, I feel NDFA does similar to Quantum Computation but we preferred to convert NDFA to DFA and solved ...
0
votes
1answer
55 views

Does quantum computing convert any O(2^n) algorithm into a polynomial running time and how?

For example, if it is a $ O(2^n) $ algorithm that loops through 0 to $ 2^n - 1 $ and check whether the number of 1 bits is divisible by 3, 5, 7, 9, 11, does quantum computing reduce it to non-...
2
votes
0answers
42 views

What does it mean this relation: $BQP^{BQP} = BQP$

I am reading this paper by Fortnow, titled: One Complexity Theorist's View of Quantum Computing. In section 4, he states the following: Bernstein and Vazirani [BV97] show that BQP can simulate any ...
3
votes
1answer
120 views

Can current quantum computers decide languages that Turing Machines cannot?

I am currently learning Computing Theory at university, and we were on the topic of Turing-Decidability, Recognizability, etc. Showing that a problem is undecidable with Turing machines due to ...
52
votes
3answers
14k views

Why did Google not use an NP problem for their quantum supremacy experiment?

Reading discussions of the recent quantum supremacy experiment by Google I noticed that a lot of time and effort (in the experiment itself, but also in the excellent blog posts by Scott Aaronson and ...
13
votes
2answers
1k views

Quantum Supremacy Task

I’m trying to understand the task performed by Google’s Sycamore that recently achieved alleged Quantum Supremacy. I’ve read the paper in Nature but the actual task that would have taken 10,000 years ...
1
vote
1answer
21 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 ...
3
votes
1answer
34 views

Does there exist any unrelativized separation between a quantum complexity class and a classical one?

I'm familiar with results of relativized separation for BPP-BQP, BQP-PH and NPC-BQP. I'm also aware that while e.g. Factoring is not believed to be in BPP, it hasn't been proven and so we're not quite ...
2
votes
1answer
69 views

BosonSampling: $\# P \subseteq FBPP^{{NP}^{\mathcal{O}}}$ implies $P^{\#P}\subseteq BPP^{{NP}^{\mathcal{O}}}$

I am a complexity beginner, actually a quantum physicist. In their famous BosonSampling paper, Aaronson and Arkhipov show amongst other things a polynomial time machine solving the problem of ...
1
vote
0answers
32 views

Which is harder, an NP-complete problem or the Raz-Tal oracle problem?

This is a (hopefully) sharper version of a question that I asked previously. Which of these algorithms is believed to have a longer asymptotic runtime? The optimal algorithm guaranteed to solve some ...
5
votes
0answers
102 views

The relationship between matrix inversion, the HHL algorithm, and the unlikely scenario that $BQP = PSPACE$

I am studying the quantum computing algorithm presented in the paper Quantum algorithm for linear systems of equations}. Without going through all the details, the HHL algorithm is able to apply an ...
1
vote
0answers
99 views

What is the complexity class of exponential parallelism?

Consider the class of problems that can be computed when you have access to exponentially many processors working in parallel. How does one capture that in a proper formalism? Is there some ...
3
votes
1answer
183 views

Basic complexity theory (in Oracle Separation of BQP and PH)

I have some basic questions about complexity theory that came up when I tried to understand the result by Raz and Tal that BQP$^O\nsubseteq$ PH$^O$. Aaronsons paper was helpful, but I still have some ...
1
vote
0answers
29 views

Questions about Seth Lloyd's Programming the Universe?

I have been interested in Seth Lloyd's cosmological model (which proposes that the universe is a computer: https://en.wikipedia.org/wiki/Programming_the_Universe, https://arxiv.org/abs/quant-ph/...
0
votes
2answers
61 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....
2
votes
1answer
52 views

Estimation of the number of solutions by Counting

This is a question from a quantum computation textbook. Consider a classical algorithm for counting the number of solutions to a problem. The algorithm samples uniformly and independently $k$ times ...
1
vote
0answers
61 views

How is the modular multiplication matrix unitary in Shor's Algorithm?

I have been reading papers about the construction of this matrix in Shor's Algorithm all night. The behavior of the controlled modular multiplication matrix is described as $$C U_{a^{2}}(|c\rangle|y\...
3
votes
1answer
77 views

Quantum vs classic in NP-hard problems

Is there any quantum algorithm (algorithm for quantum computers) for any NP-hard problem that has better runtime than the best known classic algorithm's runtime?
1
vote
0answers
25 views

Use Less Qubits to simulate More Qubits

Lots of (quantum) applications need thousands of qubits. But suppose we are short of stable qubits, is it possible (in general) using more time (or classical computation resources) to made up this ...
2
votes
1answer
152 views

Why have quantum circuits won out over quantum Turing machines?

As I understand it, quantum circuits as a model are equivalent to quantum Turing machines, or at least they can be simulated on each other. So my question is, why have quantum circuits become the ...
1
vote
0answers
53 views

Computational power of quantum finite automata

I am preparing some lecture notes on the computational power of quantum finite automata (QFA). I am a bit confused about which models of QFA are stronger and which models are weaker than standard ...
8
votes
2answers
1k views

Does this article imply that Turing-Computability is not the same as “effectively computable”?

I've stumbled across this article. It says that there is a problem that only Quantum Computers can solve. In my understanding, this should mean, intuitively, that this problem is "effectively ...
2
votes
1answer
43 views

On the robustness of BQP class

Typically the notion of quantum Turing machine is introduced with its transition function. $$ \delta:Q\times \Gamma\rightarrow \mathbb{C'}^{Q\times \Gamma\times\{L,R,0\}} $$ Where $\mathbb{C}'\...
0
votes
2answers
34 views

Deustch algorithm using one qubit

Deutsch algorithm uses two qubits to determine the type of function. But what if we have only one qubit? How the algorithm would be implemented? And especially, how $U_f = |x\rangle |y \oplus f(x)\...

1
2 3 4 5