Stack Exchange Network

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

2
votes
1answer
36 views

Deutsch–Jozsa algorithm: why is $f$ constant?

I'm trying to understand how the Deutsch–Jozsa algorithm works with the following circuit: Circuit in Quirk Since we have the top 2 wires measuring $|0\rangle$ with 100% probability, it means $U_f$ ...
4
votes
1answer
56 views

Quantum speedup without entanglement

Is there an instance of a quantum algorithm that is faster than its classical counterpart, but doesn't use entanglement, only superposition?
2
votes
1answer
43 views

Estimation of Z in the quantum Euclidean algorithm

In this paper there is a quantum algorithm that can estimate the distance between a given vector U and a set of vectors V (by taking the mean). In some part of the algorithm, we need to find the sum ...
2
votes
3answers
103 views

Swap Test for vector difference - how are different sized inputs combined?

I'm working on a similar problem of that raised by Aman in Inner product of quantum states Concerning the use of Swap Test for calculating the difference of two vectors. An example of the original ...
5
votes
1answer
57 views

What is the hidden subgroup in Simon's problem?

Given access to an oracle for a function $f:\{0,1\}^n\to\{0,1\}^n$ such that $f(x)=f(y)$ iff $x\oplus y\in\{0,s\}$, Simon's algorithm allows to recover $s$ in $\mathcal O(n)$ queries to the oracle. ...
5
votes
1answer
60 views

Durr and Hoyer's: A Quantum Algorithm for Finding the Minimum

I'm trying to understand this algorithm: arXiv:quant-ph/9607014 and I already have a problem on page 1, when they say that initializing the memory and "marking the elements $j$ such that $T[j]<T[y]$...
4
votes
1answer
55 views

Adapting search algorithm to search the minimum in a database in $O(\sqrt{N}\log(N))$ queries

I need some hint on how to adapt grover's algorithm to search the minimum in a database with $N=2^n$ elements in $O(\sqrt{N}\log(N))$ queries with probability of success $\geq 2/3$. I know I can do it ...
2
votes
1answer
64 views

How do you implement the gates for Grover's algorithm for more than 4 elements?

I am currently working intensively on the Grover algorithm and have understood the individual "building blocks" of the algorithm so far. There are also references in the literature to Nielsen, e.g. an ...
5
votes
3answers
98 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 ...
2
votes
0answers
31 views

Grover's algorithm and Battleship solution

I have read that quantum computers are not known to be able to solve NP-complete problems in polynomial time. However, if you consider a game of Battleship with grid size $X, Y$ and represent this by ...
2
votes
2answers
45 views

Computing max of $2$, length $n$ bit registries

Define a quantum algorithm that computes the maximum of two $n$-qubit registers. From Quantum Computing: A Gentle Introduction (Eleanor Rieffle & Wolfgang Polak), exercise 6.4.a (page 121). I ...
0
votes
1answer
32 views

Why do we search for square roots of 1 in Shor's algorithm unlike the qudratic sieve?

In the quadratic sieve algorithm, the idea is to find $a$ and $a$ such that $a^2 \equiv b^2 \bmod n$. We need that $a\not\equiv \pm b \bmod n$. However, there the $c$ is not necessarily $1$. $\gcd(b \...
1
vote
1answer
42 views

Confusion regarding probability of period resulting in factoring

This is a sequel to How does $x^{\frac{r}{2}} \equiv -1 \pmod {p_i^{a_i}}$ follow from "if all these powers of $2$ agree"? Polynomial-Time Algorithms for Prime Factorization and Discrete ...
4
votes
1answer
28 views

How does $x^{\frac{r}{2}} \equiv -1 \pmod {p_i^{a_i}}$ follow from “if all these powers of $2$ agree”?

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (Shor, 1995) [p. 15] To find a factor of an odd number $n$, given a method for computing the order $...
3
votes
1answer
57 views

Validity of the Grover Iterator

I am interested in showing the validity of the Grover operator. Now there are several ways to show it. One way is with complete induction. It has to be shown that the following relationship applies: $...
1
vote
3answers
181 views

How to prove teleportation does not violate no-cloning theorem?

For a given teleportation process as depicted in the figure, how one can say that teleporting the qubit state $|q\rangle$ has not cloned at the end of Bob's measurement?
2
votes
0answers
20 views

How to apply unitary coupled cluster to a spin problem?

I understand how to apply UCC to a problem formulated in a second-quantized (fermion) form: you start with some state and then create a unitary operator out of single-body (or double-, triple- and so ...
3
votes
1answer
51 views

Creating an ansatz for variational quantum algorithms?

I was recently reading through the tutorial on the Cirq documentation about creating variational quantum algorithms, and I came to the section on ansatz preparation. The way that the ansatz is ...
5
votes
0answers
113 views

Circuit construction for Hamiltonian simulation

I would like to know how to design a quantum circuit that given a Hermitian matrix $\hat{H}$ and time $t$, maps $|\psi\rangle$ to $e^{i\hat{H}t} |\psi\rangle$. Thank you for your answer.
1
vote
2answers
79 views

Is there a way to reverse the amplitudes of a quantum system?

For example in grover search algorithm, assuming that the amplified amplitude is $\alpha$ , is it possible to perform this operation : $\alpha |0...\rangle + \beta |1...\rangle \longmapsto \beta|0...\...
4
votes
1answer
57 views

Garbage-Free Reversible Binary-To-Unary Decoder Construction

In designing reversible circuits one of the useful circuits is the decoder. The operation of a decoder is naturally reversible, so it makes sense to be able to create one with no garbage outputs. ...
12
votes
0answers
117 views

Quantum machine learning after Ewin Tang

Recently, a series of research papers have been released (this, this and this, also this) that provide classical algorithms with the same runtime as quantum machine learning algorithms for the same ...
4
votes
1answer
85 views

Why do we use the quantum superposition for a period instead of factors in Shor's algorithm?

I understand in Shor's algorithm we use quantum computers to find the period of a function which can then be used to find N, and we increase the probability of observing the state with the correct ...
7
votes
2answers
94 views

Equivalent unitary transformations

Suppose $x \in \{0,1\}^n$. The standard way to make a query is with an oracle $O_x$ that given an input $|i,b \rangle $ returns $|i,b \oplus x_i \rangle$. Via the phase kick-back trick, this can be ...
5
votes
2answers
66 views

Constructing a circuit which performs the transformation $|x,y\rangle$ $\rightarrow$ $|x, x + y\text{ mod } 4\rangle$

When faced with exercises like these, I find it hard to know how to construct the circuits due to the amount of input one needs to account for. I have seen the solution provided here however, I don't ...
9
votes
2answers
151 views

Does Shor's algorithm end the search for factoring algorithms in the quantum world of computation?

In other words, will factoring research remain solely in the classical world or are there interesting research on-going in the quantum world related to factoring?
5
votes
1answer
86 views

How exactly does modular exponentiation in Shor's algorithm work?

Consider the modular exponentiation part of Shor's algorithm which in many works is just referred to as $$U_{f}\sum^{N-1}_{x = 0}\vert x\rangle\vert 0\rangle = \vert x\rangle\vert a^{x}\text{ mod }N\...
3
votes
1answer
129 views

Is there a polynomial quantum algorithm for graph coloring?

Is there a polynomial time and polynomial space quantum algorithm for finding a 4 colouring of any loopless planar graph?
2
votes
0answers
52 views

Possible results from Shor's algorithm in practice

After reading through Shor's algorithm, I have a few questions about the probability of factoring semiprime number out. Here is some background of the question. To factor a semiprime number $N$ such ...
8
votes
2answers
2k views

Why is quantum Fourier transform required in Shor's algorithm?

I’m currently studying the Shor’s algorithm and am confused about the matter of complexity. From what I have read, the Shor’s algorithm reduces the factorization problem to the order-finding problem ...
4
votes
2answers
51 views

Is the $|-\rangle$ state the only one that can do the trick for Grover's algorithm?

$\newcommand{\qr}[1]{|#1\rangle}$Grover algorithm's input is a superposition, representing the haystack, and the Bell state $\qr{-}$. The $\qr{-}$ seems utterly important: when I replaced $\qr{-}$ by,...
2
votes
0answers
100 views

What is the complexity of the quantum phase estimation in Grover's algorithm?

Suppose we are using GA (Grover's algorithm) such that we are given it has 2 or more solutions. The search space is of size $N$. We all know Grover's algorithm has, at worst, a time complexity ...
2
votes
2answers
129 views

What is the actual mechanism behind quantum computing?

I was redirected from theoretical computing to quantum computing for this question. I've been mildly researching quantum computers to figure out how entanglement and superposition are utilized for ...
4
votes
2answers
50 views

Simon's Algorithm - Probability that the measurement results in a string Y

I found something in a lecture on Simon's algorithm that I do not quite understand how to interpret. There the following is said: $$\sum_{y\in\{0,1\}^n}|y\rangle\left(\sum_{x\in\{0,1\}^n} (-1)^{x\...
3
votes
1answer
302 views

In Simon's algorithm, why is $f$ one-to-one if (and only if) $s=0^n$?

I'm dealing with Simon's algorithm a bit and "stumbled" upon something called for the algorithm. It is said that if the period is $s = 0^n$, then it is an injective function, that is, a 1 to 1 ...
4
votes
1answer
48 views

Grover's algorithm oracle matrix

I'm trying to implement Grover's algorithm in pyQuil, but I'm having trouble creating the oracle matrix given the function $f$, where $f(x)=1$ if $x=w$ and $f(x)=0$ otherwise. In most of the ...
2
votes
1answer
44 views

Grover algorithm for more than one element

I am currently working on the Grover algorithm again. In many lectures and documents, as well as books, I noticed that there is always talk of looking for a single element of $N$ elements. Now I read ...
3
votes
0answers
42 views

Optimal sampling strategy for VQE

In VQE we wish to minimize some cost function $F(\vec{x})$ that is dependent on a quantum state $\left| \psi_\vec{x} \right>$ which is prepared by a unitary $U(\vec{x})$ depending on some (...
2
votes
0answers
52 views

Does Brassard's algorithm for calculating the mean make implicit assumptions on distribution?

In An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance Brassard presents a quantum algorithm for finding ...
4
votes
1answer
71 views

Grover operator as a rotation matrix

I have seen that it is possible to represent the Grover iterator as a rotation matrix $G$. My question is, how can you do that exactly? So we say that $|\psi\rangle$ is a superposition of the states ...
3
votes
1answer
79 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 ...
3
votes
1answer
49 views

Aren't reversible logic gates a necessity for efficiently executing quantum algorithms?

The Wikipedia article on logical reversibility says: ...reversible logic gates offered practical improvements of bit-manipulation transforms in cryptography and computer graphics. But I guess ...
3
votes
2answers
79 views

Grover algorithm phase shift and steps

I am currently working on the Grover algorithm and have a few questions. In the third step of the algorithm, a phase shift is performed on all states, except $|0\rangle$. My question is, why is the ...
2
votes
1answer
42 views

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

I'm trying to understand the Deutch-Josza algorithm from adiabatic perspective as presented in Adiabatic quantum computing A: Review of modern physics, vol 90, (2018) pp 015002-1 (arxiv version). ...
5
votes
1answer
50 views

Query lower bound for Majority function using the quantum adversary method

Using the quantum adversary lower bound technique, how can one calculate lower bound for Majority function $f:\{0,1\}^n \to \{0,1\}$ such that $f(x)=0$ if $|x|\leq n/2$ else $f(x)=1$, $|x|$ is the ...
4
votes
1answer
171 views

Intuitive Proof: BQP ⊆ PP

Promise Problem : It is a pair $$\mathcal{A}=\{\mathcal{A}_{\text{yes}},\mathcal{A}_{\text{no}}\}$$ where $\mathcal{A}_{\text{yes}}$ and $\mathcal{A}_{\text{no}}$ are disjoint sets of inputs (yes ...
6
votes
0answers
78 views

What is recursive Fourier sampling and how does it prove separations between BQP and NP in the black-box model?

Context: I was going through John Watrous' lecture Quantum Complexity Theory (Part 1) - CSSQI 2012. Around 48 minutes into the lecture, he presents the following: No relationship is known between $...
2
votes
1answer
53 views

Deutsch algorithm with equal input bits

I am currently working on the algorithm of Deutsch. The algorithm defines two starting states, which are for $|x\rangle = |0\rangle$ and for $|y\rangle = |1\rangle$. So far, that's clear to me. But ...
1
vote
0answers
53 views

Extrapolation of CRISPR

Can quantum computing do a simple simulated extrapolation of CRISPR (clustered regularly interspaced short palindromic repeats) projects using a limited number of variables? I mean something like ...
5
votes
0answers
85 views

How many qubits and how many gates, are required for finding the eigenvalues of a matrix?

Say I have an $N \times N$ matrix and I want to know the eigenvalues to a precision of $\pm \epsilon$. How many qubits and how many gates do I need?