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.

2
votes
0answers
21 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
27 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
52 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
49 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
36 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
65 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
22 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 ...
0
votes
2answers
58 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
30 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
38 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
15 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
71 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
44 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
47 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
160 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
53 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
31 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
36 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
72 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
243 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
42 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
44 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
49 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
86 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
81 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
19 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
33 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
189 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
89 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
51 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
49 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
208 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 ...
3
votes
3answers
86 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
128 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
307 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
151 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
70 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
127 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 ...
4
votes
0answers
30 views

Quantum algorithms for logical inference - reference request?

Microsoft is committed to the building of the scalable, industrial size topological quantum computer, Visual Studio integrated programming language and SDK will be released by the end of this year (...
5
votes
3answers
1k views

Is there a formalization of the computational model for quantum computers?

There are several equivalent computation models, each capable of simulating each other. For example, the lambda calculus or the SKI calculus which are based on rewriting, Cardelli's object calculus, ...
1
vote
1answer
63 views

Quantum Computing Superposition

Disclaimer: By asking this question i'm assuming that "memory" on a quantum computer works similarly compared to a regular computer in the sense that you can store information deterministically and ...
4
votes
1answer
351 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)$ ...
-1
votes
1answer
55 views

Is this possible to find the maximum of differentiable and analytic function on finite and fixed interval in O(1) time using quantum computer?

$f$ is differentiable (continous) and analytic function. If $x\in\mathbb{R} \land 0\le x\le1$ then $f(x)$ is computable, $f(x)\in\mathbb{R}$ and $0\le f(x)\le1$. I have a conjecture that it is ...
3
votes
1answer
128 views

Can quantum computer compute the sum of $n$ natural numbers in $\Theta(\log n)$ time?

Classical computer always requires no matter what $\Theta(n)$ time to compute the sum of $n$ natural numbers, but can quantum computer do that in $\Theta(\log n)$ time? Given that $a$ is an infinite ...