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
3
votes
0answers
20 views

Proof that quantum entanglement does not increase the asymptotic capacity of classical channel

Consider a classical channel $N_{X\rightarrow Y}$ which takes every input alphabet $x\in X$ to output alphabet $y\in Y$ with probability $P(y|x)_{Y|X}$. It is stated in many papers that even if the ...
2
votes
0answers
19 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
52 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 ...
0
votes
0answers
11 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 ...
52
votes
3answers
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 ...
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
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 ...
3
votes
1answer
28 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
46 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
19 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 ...
0
votes
0answers
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,...
4
votes
0answers
92 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 ...
0
votes
0answers
48 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
75 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
27 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
44 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
40 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
33 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
52 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
21 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
0answers
62 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
30 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”?

First of all, I apologize if this has been asked, but I truly didn't find anything. I've stumbled across this article. It says that there is a problem that only Quantum Computers can solve. In my ...
2
votes
1answer
35 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
31 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
vote
2answers
223 views

Quantum NAND gate

Wondering how a quantum NAND gate would be implemented, and if it would be considered universal. I saw for quantum computing the Hadamard, phase, CNOT and π/8 gates are universal, but didn't see NAND ...
2
votes
1answer
39 views

How to perform measurement of a qubit?

I am trying to implement the Deutsch algorithm. My steps were: Write down $|01\rangle$ in a matrix form $A$; Apply $H^{\oplus2}$ gate to $A$ matrix; Multiply it with $U_f$ matrix; Apply $H$ to the ...
4
votes
1answer
77 views

Grover's Algorithm result when the desired element is not present

What does Grover's algorithm output when the desired element is absent from the database? Since there will be no phase inversion, how exactly will the probabilities work?
1
vote
1answer
61 views

Are physical laws uncomputable in any type of computation (according to this article)?

It seems that this article (https://arxiv.org/pdf/1312.4456.pdf) proposes that laws of physics are uncomputable (i.e., they could not be reproduced on a computer), but I'm not sure about it. In some ...
1
vote
1answer
115 views

Grover algorithm when element not present in the array/database

I've been reading about the Grover algorithm for finding elements in an unstructured database by the means of quantum computing, and even done some exercises. What I don't understand (and can't find ...
0
votes
1answer
51 views

In the shor's quantum circuit, what is the transformation of the modular operating gates?

I know different parts of this circuit, just I have a problem with that part that I circled in picture. I want to know the function of that part. If you have useful information about it, please ...
1
vote
2answers
91 views

Hadamard transformation and measurement of one qubit

I also came across something, which is not completely understandable for me, so I ask here. Given is a qubit in an entangled state, this is: $$ \frac{1}{\sqrt{2}}(\left|00\right>-\left|11\right>...
1
vote
0answers
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, ...
2
votes
1answer
50 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 ...
0
votes
1answer
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.
2
votes
2answers
80 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, ...
4
votes
1answer
36 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? ...
2
votes
1answer
51 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 ...
1
vote
1answer
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: ...
0
votes
1answer
68 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 ...
2
votes
1answer
67 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 ...
2
votes
2answers
192 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 ...
2
votes
1answer
31 views

Is there a complexity class “BQP without error”?

I was wondering if there is a complexity class for problems that can be solved efficiently by a quantum computer such that it always gives the right answer? For example the Deutsch-Josza algorithm ...
0
votes
1answer
57 views

Turing machines and their computational power

Is Turing machine most powerful model of computation? Is it possible theoretically to build the model of computation which is more powerful than TM i.e is it theoretically possible to build the ...
0
votes
1answer
34 views

Rows and columns in quantum-gate matrices read the same - why?

I have noticed that for all the matrices representing quantum gates, if we read rows left-to-right and top to bottom, the read the same as columns top to bottom left to right. Example: \begin{...
3
votes
1answer
46 views

Shor's algorithm and offset elimination

I am wondering if the second Quantum Fourier Transform (QFT) in Shor's algorithm is necessary. I am probably missing a point but it seems that an offset elimination function would suffice to determine ...
2
votes
1answer
79 views

Reversible computation and no cloning theorem in quantum computing

I am having a problem in understanding a conflict between reversibility in quantum computation and the No cloning theorem. Given a function f, we construct the reversible version of f by adding ...
1
vote
1answer
332 views

How to apply a Hadamard gate to one qubit in a 2-qubit system?

Edit: I've pinpointed that the difference between solutions occurs when I apply the $H$, up to there, the solutions match. So, perhaps it is better to phrase my question as: how to apply an $H$ gate ...
3
votes
0answers
58 views

Simon's algorithm in quantum computing

I am curios how simon's algorithm works and I have read this post Simple explanation of Simon's Problem but still is not clear for me. I have found on th internet this example https://www.cs.vu....
1
vote
1answer
68 views

A restatement of Moore's law that takes into account quantum computing

The first line of the Wikipedia article on Moore's law states that Moore's law is the observation that the number of transistors in a dense integrated circuit doubles about every two years As ...