Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
0answers
28 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
32 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
20 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
50 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
26 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
0answers
24 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
28 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
63 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
35 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
60 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
48 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
82 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
34 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
76 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
35 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
41 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
73 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
46 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
26 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
60 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 ...
1
vote
2answers
167 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
27 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
55 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
32 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
37 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
74 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
270 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
47 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
54 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 ...
2
votes
0answers
50 views

Are there problems for which quantum computers don't even give a (nontrivial) polynomial speedup?

This question is in a sense the converse of Will quantum computers out-scale classical computers at P-problems?. We know that there are oracle problems (e.g. unstructured search) for which we can ...
4
votes
2answers
89 views

Should we always think of problems higher in the polynomial hierarchy as harder than problems lower in the hierarchy?

This "research vignette" (whatever that is) claims that the polynomial hierarchy classifies problems according to a natural notion of logical complexity, and is defined with an infinite number of ...
1
vote
1answer
91 views

Question about H-gate on entangled qubits

I have a question about the Hadamard Gate on entangled qubits. I’m very newb to quantum computing and does not have any professional knowledge in physics nor mathematics. However I’ve tried some ...
0
votes
0answers
22 views

Grover's search on cryptographic hash functions - how can we build the oracle? [duplicate]

Let's say I'd like to search a database and I have a function $f$ such that $f(x) = 0$ for all incorrect entries and $f(x) = 1$ for all target entries. The crux of Grover's search seems to be that ...
2
votes
1answer
35 views

Difference between CNOT and 2nd bit bitflip

I understand how the outcome of each is supposed to be different, but in matrix form are these gates not the same? The CNOT matrix negates the second bit regardless of the input of the first.
2
votes
1answer
203 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. ...
2
votes
0answers
91 views

Simulating QC using nondeterministic Turing machine

Is it more efficient to simulate Quantum Computer using a non-deterministic Turing machine? Would it be more efficient than simulation using a deterministic Turing machine or probabilistic Turing ...
1
vote
0answers
53 views

How does this last step in Shor's algorithm work?

Page 854 of The Nature of Computation states the following (This discussion has made the simplifying assumption that $M/r$ is an integer): If each of the observations gives us a random harmonic, ...
3
votes
1answer
50 views

How is this definition of the quantum Fourier transform to be understood?

In regards to the quantum Fourier transform Page 845 of The Nature of Computation states The amplitudes $\tilde{a}_\mathbf{k}$ are the Fourier coefficients of $a_\mathbf{x}$, $$\tilde{a}_\mathbf{...
1
vote
1answer
229 views

Quantum oracle in Grover's problem?

Here's the exact problem I'm having with Grover's search algorithm.. Given a function f:{0,...,N-1} -> {0,1}, Grover's problem is to find x such that f(x)=1, provided that there exists such x. The ...
2
votes
3answers
90 views

Quantum computing - Difference between a binary bit and a Q-bit

I have recently watched this introductory video on quantum computing where the speaker talks about $n$ Q-bits and the representation of $2^n$ states. What I didn't get is the word state.How is it ...
0
votes
1answer
61 views

Computational power difference between all interconnected qubit vs few interconnected qubit

Recently I came across some news that Google and IBM are planning to unveil a 50 qubit quantum computer. I read that in this design, each qubit is not connected to all other qubits rather only to the ...
1
vote
2answers
138 views

How is it possible to compare $P$ class with $BQP$?

BQP : (bounded-error quantum polynomial time) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. Question ...
5
votes
1answer
338 views

Traveling Salesman — number of qubits required?

I'm trying (in vain) to get a beginner's grasp of quantum computing, so doing a lot of reading. I've started looking at IBM's QISkit Jupyter Notebooks, and came across the one on MaxCut problems. In ...
1
vote
1answer
153 views

IBM was able to simulate a 56 qubit quantum computer using only 3 TB of memory

Recently it's been in the headlines that IBM was able to simulate a 56 qubit quantum computer using only 3 TB of memory. This is several thousand times smaller than one would expect the memory ...
0
votes
1answer
72 views

Solving simultaneous multiple chinese remainder theorem on the quantum computer - possible?

Is it possible to solving simultaneous multiple chinese remainder theorem on the quantum computer? We have $k$ variables. Each variable can take two values. The question is: can we calculate all ...
1
vote
0answers
149 views

Are there quantum algorithm that solve the boolean satisfiability problem in subexponential time?

Are there quantum algorithms that solve the boolean satisfiability problem in subexponential time? Do they just give a determination as to whether an expression can ever evaluate to true, or can they ...