Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

Filter by
Sorted by
Tagged with
0
votes
1answer
1k views

Differences between Quantum Computing and Parallelism [closed]

What are the differences between Quantum Computing and Parallelism? thanks in advance
0
votes
1answer
255 views

Finding all solutions by Grover search(not superposition)

When there are multiple marked elements, grover search provides only superposition of them. If I want to find all the marked elements, not superposition, I could try this: 1) Do Grover search, get ...
0
votes
1answer
85 views

Question about discarding the second register in the standard approach of hidden subgroup algorithm

My questions: What does discarding the second register mean for the standard approach of hidden subgroup algorithm? Why does discarding let the first register end up in a mixed state? My ...
0
votes
1answer
63 views

Grover's algorithm, M out of N, when M is large

The more general version of Grover's algorithm searches for one of $M$ entries that match a criterion, out of $N$ total entries. I have seen it written that this takes $O(\sqrt{N/M})$ iterations, to ...
0
votes
1answer
90 views

Confusion with the proof of constraints for a particular adiabatic quantum evolution

[This might be related to one of my previous unanswered questions.] This proof belongs to the paper, How to Make the Quantum Adiabatic Algorithm Fail by Edward Farhi, Jeffrey Goldstone, Sam Gutmann ...
0
votes
1answer
95 views

How are new probabilities computed when simulating measurement on a set of qubits?

Suppose I have a set of 3 qubits and I have the probabilities for their distribution. This could be arbitrarily entangled or pure: |000> -> a |001> -> b |010> -> c |011> -> d |100> -> e |101> -> f |...
0
votes
1answer
259 views

Quantum Fourier Transform question regarding measurement

When we use the quantum fourier transform, for a function, the output is entangled, so if a measurement is made on the output, the result may not be that of the function that one wanted in the first ...
0
votes
1answer
131 views

How does one extend local checkability to quantum complexity classes?

How does one extend local checkability to quantum complexity classes like BQP? Or are quantum algortihms inherently holistic?
0
votes
0answers
149 views

Questions about the definition of the Quantum Turing Machine

I am trying to have a better understanding of the definition of the Quantum Turing Machine. My questions: If the output of a quantum program is the eigenvalue of the ground state of a Hamiltonian ...
0
votes
0answers
94 views

What is the relationship between quantum tomography and quantum error correction?

To realize correct quantum computing it seems that both quantum error correction and quantum tomography would be necessary. Is this true? What is the relationship between these two fields?
0
votes
0answers
29 views

Hardness of finding similar (quantum) states

Consider a quantum state $\lvert \psi \rangle$, we know from the no cloning theorem, that it cannot be perfectly cloned. Also, loosely speaking, that it can be imperfectly cloned s.t. one can produce ...
0
votes
0answers
124 views

Determining if a function is constant or not using period finding

Consider an arbitrary boolean function $$f: {\lbrace 0,1 \rbrace}^n \rightarrow \lbrace 0,1 \rbrace$$ which we write as: $$f(x_1, x_2 ... x_n) $$ where each $x_i$ is a boolean variable We note ...
0
votes
0answers
123 views

Computing the period of a function using a quantum computer

Consider a blackbox function $$f(x): Z \rightarrow \lbrace 0,1 \rbrace $$ Which inputs an integer and outputs 0 or 1 with bit complexity n. If the period P of this function satisfies $$P \in O(2^{...
0
votes
0answers
383 views

Is it possible to add quantum physics theory to traditional machine learning algorithms to get more accurate results

Lets suppose your data set includes locations in several dimensions and the kind of entity which is the class of the data set, is there other kind of information you need to add (such as times, ...
0
votes
1answer
183 views

What would be a complete QC circuit?

In classical computing NAND is a complete set (functionally complete) of binary operations, namely any Boolean circuit can be expressed using NAND gates. Is there an equivalent for quantum computing ...
-1
votes
1answer
50 views

QMA definition of difference between probabilities intuition

I'm reading about the complexity classes related to quantum computation, currently I'm studying QMA class. A language is in QMA(c,s) if there exists a polynomial time verifier and polynomial $p(n)$ ...
-1
votes
2answers
280 views

Will we be able to use the current software in quantum computers? [closed]

I'm not sure if this should go here, so my apologies. The fact is that lately I have heard a lot about quantum computers and that they are not that far away. As it is a totally new technology, which ...
-2
votes
2answers
249 views

How can I get $\sum_n e^{i a_n} |n\rangle$ from $\sum_n a_n |n\rangle$?

Suppose that I have a normalized quantum state $\sum_n a_n |n\rangle$, is there a quantum operation/circuit so that I can get $\frac{1}{N} \sum_n e^{i a_n} |n\rangle$ at output? How?
-2
votes
1answer
1k views

Addition on a quantum computer

From reading https://arxiv.org/pdf/quant-ph/0008033v1.pdf 3n qubits are required to add two n bit numbers. For a simple arithmetic operation such as a+b+c+d where ...
-2
votes
0answers
66 views

Is BQP upper bounded by the class of problems computable by an exponential number of GPUs?

Consider the class $EXPGPU$ that informally contains all problems that can be stocastically solved in polynomial time by an exponential number of processors. Question: Is $BQP \subset EXPGPU$? My ...
-2
votes
1answer
140 views

Complexity class on quantum computation and classic ones

Does the complexity speedup in superpolynomial by quantum computation mean it is possible to find new algorithm on classic Turing Machine which can speedup in classic Turing Machine in ...
-3
votes
1answer
136 views

Dimension of the Fourier transform for $S_5$ [closed]

My question: What is the dimension of the Fourier transform for $S_5$? My effort: The dimensions of the seven irreps of $S_5$ are $1,1,4,4,5,5,6$. According to the notes of Andrew Childs, the ...
-3
votes
2answers
392 views

Understanding function controlled NOT gate

...
-3
votes
1answer
179 views

The factoring problem reduces to order finding or is it the other way around? [closed]

initially i was not at all equipped in theoretical computer science and knew only basics of number of theory. I started working from scratch on the age old problem of primality testing which led me to ...
-3
votes
1answer
163 views

Lower bounds on $Q_{\epsilon}(IP)$

I want to show that $Q_{\epsilon}(IP) \geq (1-O(\epsilon))n$, where $IP:\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ is the usual mod 2 inner product. I have Nayak's lower bound, but I am not sure ...
-4
votes
1answer
126 views

Can a computer generated organism be self aware? [closed]

Imagine that a computer generating a small universe similar to our own. Same table of elements, same physics, ect. Starting from the very beginning, with the creation of all the atoms in the ...
-6
votes
1answer
205 views

Is the sub-bit model of quantum computation equivalent to other models? [closed]

In a comment to this question Peter Shor asked me for a reference about the third described in the question point of view, namely, that quantum computers can be described as computers that can ...
-6
votes
1answer
341 views

Quantum complexity class vs classical complexity class [closed]

What is the relation between BQP complexity class and P and NP?
-7
votes
1answer
3k views

Travelling sales man with Quantum Computers [closed]

I know that it takes billions of years to solve the travelling sales man when n = 25 (Number of cities). I am wondering how fast can a quantum computer solve the travelling sales man problem (for ...
-8
votes
1answer
428 views

Duality computers

There is a lot on the internet about quantum computers and how they could factor integers. However, there is a type of computer which also uses the principles of quantum mechanics, which can be used ...