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

221 questions
Filter by
Sorted by
Tagged with
69 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 ...
11 views

### noise related to quantum cryptography

How would you define noise when talking about quantum cryptography? Is it right to say that since quantum states are susceptible to interaction with the environment there might be errors in ...
20 views

### true randomness, CHSH game and QKD protocol

Is it correct to say that there's a connection among the CHSH game concept and the QKD protocol? Given the following CHSH equation a⊕b=x∧y, if it holds a large ...
51 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 ...
47 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 ...
14 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 ...
37 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-...
24 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 ...
66 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 ...
12 views

### What is the use of relays in Harvard mark 1 (early electromechanical computer)?

First when I came to know that Harvard mark 1 had relays I thought that the relay were used like today's transistors for the purpose of processing. But I came to know that Harvard mark 1 had 5hp ...
13k 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 ...
1k views

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 ...
17 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 ...
29 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 ...
49 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 ...
22 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 ...
9 views

### Un-compute an operator given its oracle access

In general, is it easy to un-compute an operator given its oracle access? I want to ask in terms of computational complexity, that is, if there's any computationally feasible way to do this, or if not,...
93 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 ...
53 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 ...
88 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 ...
28 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/...
54 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....
41 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 ...
38 views

41 views

### Quantum and classical time complexity

Do we know any function which has same quantum and classical time complexity (bounded error), or at least same upper bound? Of course, let's rule out trivial functions like the constant function, ...
54 views

### Are hash functions really quantum resistant for commitment schemes?

It is commonly stated that hash functions remain secure in a post quantum world, the justification being that a quantum computer only has the advantage of Grover's search to give it a quadratic ...
16 views

### Simple question on the phrasing on a PBS Infinite Series video

What does she mean by finding the 6 qubit quantum state $|010001\rangle$ from a sphere of dimension $2^6$. Here is the link: https://www.youtube.com/watch?v=IrbJYsep45E at time 8:47.
83 views

### Why can’t a qbit be both entangled and in a pure state?

Not sure if I should ask this on CS or physics SE, but here goes. I’m reading on quantum computing, and one thing that keeps confusing me is the following basic fact about QM: Say we have a qbit A, ...
37 views

### what’s wrong with this quantum key distribution scheme?

I’m reading about the BB84 quantum key distribution scheme, and I’m surprised that it’s conceptually more complicated than seems necessary to me. What’s wrong with this conceptually simpler scheme? ...
52 views

### What would remain of Quantum Computing if quantum states were real numbers?

This question is motivated by my attempt to understand quantum computing and the source of its computational power. Quantum statest are described by complex numbers. That is, 1 qubit is described by ...
32 views

### Proof that a quantum computer is equivalent to some logical circuit

My question is about the quantum computer. I have tried to prove that the quantum computer is equivalent to some logical circuit. I know this has already been proven, but I will present my attempt: ...
71 views

### QTM & Halting problem [duplicate]

"Can QTM (Quantum Turing machine) solve halting problem" Why not have an immediate answer "No QTM Can't do this", we know that Turing proved it impossible when DTM , i meant , " Why we cant use the ...
68 views

### Is my interpretation correct?

I am trying to implement the algorithm described in the paper A quantum-inspired classical algorithm for recommendation systems. This is the algorithm: These are the necessary definitions for ...
206 views

### Can hypercomputation compute all kinds of incomputable numbers/functions/problems…etc?

Hypercomputation is a "cheat" that extends the capability of a Turing machine or quantum computer or cellular automaton by adding extra abilities. A standard method is "Oracle machines", Turing ...