Questions tagged [algorithm]

For questions on quantum algorithms. That is, algorithms which in theory can be executed by quantum computers, usually the computers providing 'universal' quantum computation.

Filter by
Sorted by
Tagged with
3
votes
3answers
117 views

Grover's algorithm in a nutshell

I am trying to understand Grover's algorithm. I read that this algorithm is able to find an entry in an unsorted list in just $\sqrt N$ steps, and needs only $\log N$ space. I understand entanglement ...
10
votes
5answers
1k views

How would I implement the quantum oracle in Deutsch's algorithm?

I am trying to simulate Deutsch's algorithm (elementary case of Deutsch-Josza algorithm), and I am not entirely sure how I would go about implementing the quantum oracle necessary for the algorithm to ...
2
votes
1answer
30 views

Expected value of a product of the Pauli matrices in different bases

I'm trying to reproduce the results of this article https://arxiv.org/abs/1801.03897, using Qiskit and Xanadu PennyLane. Particularly, this part with expected values of the Pauli operators: For ...
1
vote
1answer
49 views

Software for Quantum Computing

From what I read classical computing evolved so quickly because of the funding-applications cycle. Even though the cost to make denser IC's was increasing rapidly, the applications were also getting ...
5
votes
3answers
325 views

Why is the application of an oracle function not a measurement?

Why is the application of an oracle function not a measurement, causing the collapse of the system? How can you know the state of the system (the input of the oracle function) without measurement?
4
votes
1answer
193 views

How does an oracle function in Grover's algorithm actually work?

I have lately been studying quantum algorithms. I have gone through the Deutsch algorithm and Grover's algorithm. There's always a function in the oracle which somehow 'recognizes' the solution ...
9
votes
1answer
326 views

Grover's algorithm: what to input to Oracle?

I am confused about what to input to Oracle in Grover's algorithm. Don't we need to input what we are looking for and where to find what we are looking for to Oracle, in addition to the ...
4
votes
0answers
20 views

Oracle for welded tree walk

There is a famous paper by Childs, et al, in which it is shown that a quantum algorithm can find the name of the exit node for a certain graph in a way that is exponentially faster than any classical ...
3
votes
0answers
32 views

Are there any quantum algorithms to compute the norm of a vector, better than the classical version (O(d), where d is dimension)

I am researching how to speedup optimization problems using quantum algorithms. Many such algoritms use the Euclidean norm of a vector. Hence, I tried to find a quantum algorithm that speedups the ...
6
votes
0answers
84 views

What are examples of non-oracular versions of famous oracular problems?

Most quantum algorithms proposed, including Deutsch-Jozsa, Simon's, Bernstein-Vazirani etc, involve querying an oracle. If I understand correctly, the speedups depend on the oracle being efficiently ...
3
votes
0answers
124 views

What can be some bachelor thesis ideas in quantum random walks? [closed]

Note: Cross-posted on Theoretical Computer Science Stack Exchange. I am an undergraduate, reading about quantum information and quantum technology. For about some time, I have been interested in the ...
2
votes
1answer
124 views

Grover diffusion operator different gates

I have two gates here for the Grover diffusion operator. The first gate is completely understandable for me, so I implemented it myself after submitting some papers that I read. This is the first ...
0
votes
1answer
95 views

If I have a state $a|0000\rangle+b|0011\rangle$, how do you change it to make $b>a$?

How to increase the amplitude of a specific quantum state? If my quantum circuit produces the state $a|0000\rangle+b|0011\rangle$, how to make $b>a$?
26
votes
3answers
2k views

Is there a layman's explanation for why Grover's algorithm works?

This blogpost by Scott Aaronson is a very useful and simple explanation of Shor's algorithm. I'm wondering if there is such an explanation for the second most famous quantum algorithm: Grover's ...
3
votes
2answers
68 views

Is the intuition of quantum parallelism always correct?

I recently read in Section 7.5.2 of Quantum Computing: A Gentle Introduction by Eleanor Rieffel and Wolfgang Polak a section in which they criticize the view of quantum parallelism in quantum ...
1
vote
1answer
45 views

Clarification of a portion of the paper Quantum Amplitude Amplification and Estimation

I am reading the paper "Quantum Amplitude Amplification and Estimation", available here (pages 4 to 7 in particular). I will try to summarize my confusion over a statement on page $7$. Suppose that $...
6
votes
1answer
193 views

Why is this implementation of the order finding algorithm not working?

I asked a question about this earlier, but I am still coming across problems in my algorithm implementation. I am trying to implement the order finding algorithm on Cirq finding the minimal positive $...
2
votes
1answer
28 views

Loading the finite precision representation of the norm of a vector into a computational register using CNOT gates

In the paper, Quantum linear systems algorithms: a primer, available here page 23, the authors discuss encoding a vector in $\mathbb{R^n}$ into qRAM. For $x \in \mathbb{R}^n$, let $|x \rangle := ||x|...
2
votes
1answer
52 views

How does the fact that the output of a quantum circuit cannot be efficiently simulated classically help for optimisation?

This question refers principally to the article where for a low-depth circuit QAOA, the output cannot be efficiently simulated classically. I am wondering how this kind of quantum supremacy matters ...
3
votes
0answers
66 views

Quantum comparator with one fixed input

I currently need to implement efficiently a quantum comparator, with one of the values that is known at generation-time. In other words, I am searching for a quantum routine ...
-2
votes
2answers
107 views

The most important quantum question , how to force a superposition qubit to collapses to an exact value? [closed]

Note: forcing a superposition qubit to collapses to 1, means cancel the other value 0 to get 1 appear Question details step by step: ...
2
votes
0answers
22 views

QAOA and symmetry effects on the angles

In this paper, QAOA on Maxcut shows symmetries that allow them to restrict their search space intervals. But how do they find such intervals knowing that in the original QAOA angles $\gamma,\beta$ are ...
0
votes
1answer
41 views

What is $\mathbb{Z}_2$ symmetry?

I encountered the notion of $\mathbb{Z}_2$ symmetry in an article. Can someone give a definition?
6
votes
1answer
113 views

What happens with first phase factor in QFT?

I'm using Mermin's Quantum Computer Science book to understand Shor's algorithm, but I can't figure out why one of the phase factors drops out of the probability for measuring a certain y. This is ...
1
vote
0answers
15 views

Ansatz Techniques to Multi-Body Physics Problems

I have been reading this paper: https://arxiv.org/abs/1906.01563v1. I am wondering: is it possible to use the idea behind quantum circuits to build classical Hamiltonians represented in the same way?...
1
vote
1answer
37 views

What does a zero state combined state vector for 2 qubits mean?

I was fiddling with the quantum circuit used for Deutsch's algorithm and I was led to a zero state as a result which is bizarre. I don't know how to explain this result. ***I'm using Nielsen and ...
12
votes
3answers
497 views

How is the Grover-Algorithm applied to a database?

Question I want to use the Grover-Algorithm to search an unsorted database for an element $x$. Now the question arises, how do I initialize index and value of the database with the qubits? Example ...
3
votes
0answers
88 views

Quantum Optimization via Quantum Label Classification in Quantum Circuits

I have been reading Farhi and Neven's paper on quantum neural networks on quantum circuits. I also found an example - albeit not ideal as pointed out by a couple of users - thank you - in here. ...
10
votes
2answers
3k views

How many operations can a quantum computer perform per second?

I want to know what time complexity is considered efficient/inefficient for quantum computers. For this, I need to know how many operations a quantum computer can perform per second. Can anyone tell ...
3
votes
1answer
67 views

Why is the second register needed to define bit flip quantum oracles in a way that distinguishes between complementary oracles?

If our input $x \in \{0, 1\}^{n}$ is given as a black box, we usually query an oracle as follows. $$O_{x}|i, b \rangle = (-1)^{b x_{i}} |i, b \rangle$$ $i = \{1, 2, \cdots, n \}$ is the index of the ...
4
votes
2answers
64 views

Does an oracle use only the eigenstates of the quantum register?

The working of a quantum oracle is still not completely clear to me and I have a few questions: As I understand it, an oracle is a unitary quantum gate and must somehow differentiate between the ...
-4
votes
1answer
58 views

What about this metaphor for quantum computing? [closed]

Suppose you have a large collection of N numbered copper coins. However, one of them is nickel but looks exactly the same as the rest. How do you find out which number the nickel coin has? Classical ...
4
votes
2answers
96 views

Phase estimation error analysis

This question is about Lemma $7.1.2$ in Kaye, Laflamme, and Mosca's textbook: Let $\omega = \frac{x}{2^n} = 0.x_1x_2\ldots x_n$ be some fixed number. The phase estimation algorithm applied to the ...
5
votes
2answers
96 views

Using the HHL algorithm to compute $A |b \rangle$ instead of $A^{-1} |b \rangle$

In the paper "Compiling basic linear algebra subroutines for quantum computers" here, they discuss (page 2 bottom right) using the HHL algorithm to multiply a vector by a matrix. However, after ...
3
votes
1answer
52 views

The possibility of recovering the matrix $A+B$ from $e^{i(A+B)t}$ for Hermitian $A,B$

In the paper "Compiling basic linear algebra subroutines for quantum computers" here, the introduction seems to imply that the subroutines covered will touch on matrix addition and multiplication, ...
7
votes
2answers
186 views

Clarification of the “Calculations” section of the (HHL09) paper

I am reading this paper entitled "Quantum algorithm for linear systems of equations" and am trying to understand a portion of the algorithm described on page 2 and in more detail in the appendix ...
2
votes
1answer
49 views

Eliminating a term of a superposition state

Is there a way of eliminating a term of a superposition state? Let's say I have the state $$\frac{1}{\sqrt 2}|00\rangle + \frac{1}{2}|01\rangle + \frac{1}{2}|10\rangle$$ What operation would I do to ...
5
votes
2answers
172 views

Quantum counting in Q#

I cannot seem to get an estimate for the number of solutions using the quantum counting algorithm described in Nielsen and Chuang, i.e. phase estimation with the Grover iteration acting as $U$. I try ...
3
votes
1answer
98 views

Counting in Q#: number of solutions

I have this program derived from Microsoft Quantum Katas for counting (see here): ...
4
votes
0answers
34 views

Can anybody explain or suggest a good reference on how to make a modular exponentiation circuit for N=15 with any coprime base?

I have read many papers related to it but in every paper, they just show the circuit of order finding algorithm for N=15, but did not explain what is the procedure to make it. It will be great if ...
4
votes
1answer
50 views

Quantum gate teleportation T gate

I am faced with the problem of teleporting certain gates using modified Bell states. For example, I have solved the problem with the $S$ gate, which is defined as following: Alice and Bob share a ...
3
votes
1answer
65 views

Why should we use inverse QFT instead of QFT in Shor's algorithm?

Why should we use inverse QFT instead of QFT in Shor's algorithm? When I tried to simulate Shor's algorithm for small numbers, I got an answer even when I used just QFT instead of inverse QFT.
6
votes
1answer
248 views

Grover's diffusion on subset of input space

Is it possible to run grover's diffusion step on a subset of the possible input space? By this, I mean is it possible to do the diffusion process with a state space isn't in a total superposition of ...
5
votes
1answer
75 views

Implementation of Grover's Algorithm (minimum spanning tree)

I am trying to solve a minimum spanning tree problem using Grover's Algorithm. To accomplish this I would need to search a list for the minimum weight or edge for each point, for example: Given the ...
3
votes
0answers
54 views

How can I express controlled unitary operation in QPE of this implementation of HHL?

I have found this implementation of HHL, and I don't understand why the controlled unitary operation is expressed in the form of $\exp(i t_0 A/2)$ and $\exp(i t_0 A/4)$. The rotation of $\pi$ and $\...
4
votes
1answer
240 views

Understanding a quantum algorithm to estimate inner products

While reading the paper "Compiling basic linear algebra subroutines for quantum computers", here, in the Appendix, the author/s have included a section on quantum inner product estimation. Consider ...
3
votes
1answer
51 views

Implementing Deutsch's problem on IBM Q composer

I tried to implement the Deutsch's problem on IBM Q but didn't get the results as expected. So here is the circuit for the Deutsch algorithm and this is my implementation on the composer: so let me ...
8
votes
2answers
268 views

Grover algorithm for a database search: where is the quantum advantage?

I have been trying to understand what could be the advantage of using Grover algorithm for searching in an arbitrary unordered database D(key, value) with N values instead of a classical search. I ...
1
vote
0answers
29 views

Which journals and conferences would be most appropriate for new number-theoretic quantum algorithms? [closed]

Non-super-slow review process and non-super-slow publication should take precedence.
1
vote
1answer
43 views

Where (in the algorithm) is the logical qubit encoded in Q.E.C?

I have a basic question about the encoding of logical information into physical qubits. I only know the 3 qubit code (I have very limited knowledge in QEC). The 3 qubit code is usually presented as: ...