Stack Exchange Network

Stack Exchange network consists of 174 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.

0
votes
1answer
13 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
0answers
10 views

How would one go about proving QMA = BQP or QMA not equal to BQP?

QMA vs BQP is regarded as the quantum version of the P vs NP problem. If one wanted to explore if they are equal or not, how would one go about trying to prove it?
0
votes
2answers
32 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
21 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
33 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
66 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
35 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
42 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
25 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
44 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
65 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
147 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
25 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
51 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
31 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
66 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
136 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
35 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
39 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
47 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 ...
3
votes
2answers
73 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
68 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
16 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
29 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
167 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
84 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
44 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
48 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
149 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
80 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
59 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
92 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 ...
4
votes
1answer
208 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
136 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
60 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
94 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
27 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
62 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
273 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
118 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 ...
1
vote
1answer
96 views

Are there any proofs that BQP is not in P?

Are there any proofs that BQP is not in P? In laymen's terms, I am asking if there is any formal proof separating the complexity class that quantum computers are presently assumed to solve ...
1
vote
1answer
122 views

How are Qubits useful?

I'm aware that a qubit can exist in an infinite number of states and that when measured it collapses into one state, with the probability of each state being directly affected by it's latitude. My ...
0
votes
1answer
82 views

Can quantum computer compute the minimal intersection DFA of numerous minimal DFAs in polynomial time using polynomial number of qubits?

Can quantum computer compute the minimal intersection DFA of numerous minimal DFAs in polynomial time using polynomial number of qubits, where the language of each given minimal DFA is finite and it's ...
0
votes
2answers
74 views

Asserting Run Time From Big O Function

Related to this, but I felt it was more appropriate to ask as a separate question: The complexity of Shor's algorithm is of order $$O\left(n^2\,\log(n)\,\log(\log(n))\right)$$ with $n$ the bit ...
0
votes
0answers
73 views

Quantum computer performing classical algorithms

According to the reference Time/Space Trade-Offs for Reversible Computation by Charles H. Bennett given by Peter Shor in https://cstheory.stackexchange.com/questions/18938/is-there-any-task-where-...
1
vote
1answer
111 views

What does it mean for a problem to be solved in polynomial time “relative to” an oracle?

I came across the following theorem in page 12 of the following pdf : There exists an oracle relative to which there is a problem solvable in polynomial time (with bounded error probability) on a ...