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
0answers
32 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
87 views

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

Note: forcing a superposition qubit to collapses to 1, means cancel the other value 0 to get 1 appear Question details step by step: ...
1
vote
0answers
16 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
37 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
108 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 ...
9
votes
1answer
313 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 ...
1
vote
0answers
14 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
33 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 ...
10
votes
3answers
419 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
79 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
65 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
58 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
45 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
94 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
91 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
47 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
183 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
163 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
88 views

Counting in Q#: number of solutions

I have this program derived from Microsoft Quantum Katas for counting (see here): ...
3
votes
0answers
29 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
45 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
59 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
244 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
68 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
53 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
230 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
46 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
234 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.
5
votes
3answers
311 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?
1
vote
1answer
41 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: ...
4
votes
1answer
35 views

Best query and memory complexity for iterated function

Assume $f(x)$ is n-bit to n-bit function. Let $F(x)$ be defined as $T$ iterations of $f(x)$, i.e. $F(x) = f^T(x)$. Quantum algorithm relies on $F(x)$; it calls it $R$ times. What is the best query ...
4
votes
0answers
40 views

How to determine the minimum number of experiments needed to compute m-many k-local Pauli expectations?

Say I have an algorithm over N qubits and I want to find the expectation value of an operator $O$ composed of a sum of mterms, each of which is the tensor product of some number of single-qubit Pauli ...
5
votes
1answer
231 views

Quantum SVM Algorithm Error on import

I am experimenting with some Qiskit ACQUA AI algorithms which require the following import statement: from datasets import * However, ...
3
votes
1answer
257 views

Implement a Hamiltonian in O(n) - exercise question

I have the following exercise to solve: Consider the Boolean function $f(x_1 . . . x_n) = x_1 \oplus \dots \oplus x_n$ where $x_1 \dots x_n$ is an nbit string and $\oplus$ denotes addition mod $2$...
2
votes
0answers
75 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 ...
4
votes
1answer
57 views

Success probability in Grover's algorithm where there are multiple targets

The Grover algorithm allows you to search for multiple elements. Assuming my search space contains four elements, if I only search for one element, I get the one I'm looking for with a probability of ...
5
votes
1answer
147 views

Proof of the optimality of Grover's algorithm

I am currently working on the proof of Grover's algorithm, which states that the runtime is optimal. In Nielsen they say, the idea is to check whether $D_k$ is restricted and does not grow faster ...
4
votes
1answer
117 views

Grover search with single query to $f(x)$ and multiple queries to $f(x) = a$

Assume $f(x)$ is an $n$ bits to $m$ bits function and we want to use Grover's search algorithm to find $x$ such that $f(x) = a$, where $a$ is some $m$-bit predetermined value. When using the ...
3
votes
1answer
118 views

What exactly makes quantum computers faster than classical computers?

What feature of a quantum algorithm makes it better than its classical counterpart? Are quantum computers faster than classical ones in all respects?
2
votes
2answers
162 views

IBM QISKit: creating a variational algorithm from zero

I would like to implement a variational algorithm (similar to VQE but with another cost function, no expectation of a Hamiltonian involved) from zero. Is there any tutorial explaining how to implement ...
4
votes
1answer
84 views

Circuit construction for execution of conditional statements using least significant bit

Suppose I have integers and encode them as binary strings for example: $$|0\rangle=|00\rangle,|1\rangle= |01\rangle,|2\rangle=|10\rangle,|3\rangle=|11\rangle.$$ Now an $n$ bit integer, say $x$, is ...
8
votes
2answers
412 views

How do quantum computers prevent “quantum noise”?

On the Wikipedia page for Shor's algorithm, it is stated that Shor's algorithm is not currently feasible to use to factor RSA-sized numbers, because a quantum computer has not been built with enough ...
11
votes
2answers
350 views

Rigorous security proof for Wiesner's quantum money

In his celebrated paper "Conjugate Coding" (written around 1970), Stephen Wiesner proposed a scheme for quantum money that is unconditionally impossible to counterfeit, assuming that the issuing bank ...
10
votes
1answer
93 views

Is there any source which tabulates quantum computing algorithms for simulating physical systems?

I was wondering if there is a source (online or review article) which tabulates recent algorithms, and their complexities, used in simulating various physical systems. Something along the lines of: ...
2
votes
1answer
60 views

How to understand Deutsch-Jozsa algorithm from an adiabatic perspective?

I'm trying to understand the Deutsch-Josza algorithm from an adiabatic perspective as presented in Adiabatic quantum computing A: Review of modern physics, vol 90, (2018) pp 015002-1 (arXiv version). ...
9
votes
1answer
2k views

What can we learn from 'quantum bogosort'?

Recently, I've read about 'quantum bogosort' on some wiki. The basic idea is, that like bogosort, we just shuffle our array and hope it gets sorted 'by accident' and retry on failure. The ...
13
votes
2answers
755 views

What is the current state of the art in quantum sorting algorithms?

As a result of an excellent answer to my question on quantum bogosort, I was wondering what is the current state of the art in quantum algorithms for sorting. To be precise, sorting is here defined ...