All Questions
Tagged with algorithms quantum-computer
26
questions
3
votes
1
answer
144
views
Grover's algorithm & using wave interference for computing
Grover's quantum search algorithm contends that it is possible to search for a specific item in an N-sized unsorted database in only $\sqrt N$ attempts. Classically, it takes N/2 attempts on average ...
- 593
3
votes
1
answer
41
views
Could we have a quantum algorithm that have the quantum speed-up, but don’t need universal gates?
When it comes to building a quantum computer, it's like we need to consider how to perform universal gates fault-tolerantly, which is an unsolvable problem so far. While Clifford gates may be easier ...
- 31
1
vote
0
answers
73
views
Is Shor's algorithm for factoring still efficient in the presence of small phase noise
Quantum Fourier transform of $|a\rangle\in H_N$
$$|a\rangle\longrightarrow\sum_{l=0}^{N-1}e^{\frac{i2\pi a l}{N}}|l\rangle$$
where $N=2^n$ and $H_N$ is $N$-dimensional Hilbert space.
The ...
- 51
2
votes
0
answers
207
views
How Do Quantum Computers Work, Like Really [closed]
I understand in plain terms superposition and entanglement, but I'm very unclear how either of these could work as a means to increase computation power.
A helpful metaphor is that of the maze. A ...
- 129
1
vote
1
answer
336
views
Number of qubits required in Shor's algorithm
People say that the number of qubits required in Shor's algorithm for factorizing $N$ should be
$2\log N$ for control register and $\log N$ for target register.
What is the reason why these numbers of ...
- 185
1
vote
0
answers
140
views
Is there a comparison table for quantum algorithms like VQE, QPE, QAOA, and so on?
I have one question: Recently, I studied about several algorithms like VQE, QPE, QAOA and so on. I would like to make some comparison tables about those algorithms, their strengths and weaknesses. If ...
1
vote
0
answers
122
views
Final Hamiltonian for Adiabatic Grover
X-Posted on Quantum-Computing Stack Exchange
In quantum computation, there is a famous algorithm to search a marked item in an unstructured database called Grover's algorithm. It achieves a quadratic ...
1
vote
1
answer
746
views
Bell State Measurement Algorithm
I'm relatively new to quantum computation and am taking a course in it. I was wondering if it is possible to code an algorithm which would be able to take an input of a 2 qubit state and perform a ...
- 21
0
votes
1
answer
401
views
Time for Quantum Computational Prime Factorisation
I ran into this graph where the red one is
$$x^3$$
and represents the number of steps as a function of factorised bits for a quantum computer. The blue graph represents the classical computer and has ...
2
votes
1
answer
375
views
Adiabatic QC: are there known difficult problems with spectral gap not exponentially decreasing?
Adiabatic quantum computers require slow evolution to maintain global minimum: $O(1/g^2)$ time, where $g$ is spectral gap: distance between two lowest energies.
The danger is that this spectral gap ...
- 960
2
votes
1
answer
289
views
Quantum Approximate Optimization Algorithm
I try to understand the 'Quantum Approximate Optimization Algorithm' (QAOA) by Farhi et al. - arXiv:1411.4028.
I understand that the solution is hidden in the unitaries, but I do not understand how ...
- 570
0
votes
1
answer
101
views
What does "given one application of a black box" mean, in a quantum-computing context?
From Kaye, Laflamme and Mosca's An Introduction to Quantum Computing:
Exercise 7.1.1 (Bernstein-Vazirani problem) Show how to find $\mathbf a \in Z_2^n$ given one application of a black box that maps ...
- 1,669
2
votes
3
answers
386
views
Where is a classical computer better than a quantum one? [closed]
Where is a classical computer better than a quantum computer? Is there any known domain where classical algorithms always beat quantum ones, say, both in terms of time and space complexity?
If yes,...
- 168
0
votes
1
answer
197
views
Assumptions in the proofs for the optimality of Grover's Search Algorithm
I was trying to understand this paper in which it is proved that Grover's search algorithm is optimal.
On page 4, beginning of section 2 of the paper the author says the following
In the proof I ...
- 3,905
6
votes
1
answer
1k
views
Deutsch-Jozsa Algorithm for Non-Balanced+Non-Constant Functions?
Note: I'd imagine this will be a simple yes/no question for people better versed in this topic than myself, but nevertheless I'll provide a bit of background first for the edification of anyone who ...
