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.

0
votes
0answers
1 view

Is the Bernstein-Vazirani algorithm dependent on the specific behavior of the oracle?

My understanding of the Bernstiein-Vazirini algorithm is as follows: 1) We have a black box oracle with secret string s. For each bit, if s_i=1 then 0 is mapped to 1 and 1 is mapped to 0. If s_i=0 ...
4
votes
0answers
91 views

Is there a BQP algorithm for each level of the polynomial hierarchy PH?

Note: Cross-posted on Theoretical Computer Science SE. This question is inspired by thinking about quantum computing power with respect to games, such as chess/checkers/other toy games. Games fit ...
3
votes
1answer
118 views

Grover's algorithm – DES circuit as oracle?

In the literature before me, the quantum oracle of the Grover algorithm is shown as a function, in which a sign change is made possible $|x\rangle\rightarrow(-1)^{f(x)}|x\rangle$. I have read that it ...
1
vote
1answer
37 views

Correct way of expressing a measurement in a different computational basis

Sometimes we find that the result we want from a quantum algorithm is expressed in terms of a basis that is different from the usual computational basis, which I will call $$ B_C = \left\{ \lvert 0 \...
4
votes
1answer
54 views

Controlled unitary from the HHL algorithm – practical implementation using Qiskit

I have a question about the implementation of the controlled unitary $e^{iAt}$, from the paper Demonstration of a Quantum Circuit Design Methodology for Multiple Regression, using the Qiskit framework....
3
votes
1answer
43 views

Reversible crypto systems for use in the Grover's algorithm

I'm working on some papers (here and here) that use the Grover algorithm to crack krypto systems like AES and SHA. I had already asked a first question here. Now, however, a new question has arisen ...
3
votes
0answers
66 views

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

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 ...
4
votes
1answer
233 views

Understanding this description of teleportation

In the context of quantum teleportation, my lecturer writes the following (note that I assume the reader is familiar with the circuit): If the measurement of the first qubit is 0 and the measurement ...
3
votes
1answer
88 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 ...
4
votes
1answer
87 views

Prove that the operator $H U_{0^\perp}H$ can be expressed as $2|\psi\rangle\langle\psi|-I$

I'm trying to solve the following problem related to the mathematical explanation of Grover's algorithm. Let $$ \lvert\psi\rangle = \dfrac{1}{\sqrt{N}} \sum_{x=0}^{N-1}{\lvert x \rangle} \,\text{,} $$...
5
votes
0answers
91 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
100 views

How to create the oracle matrix in Grover's algorithm?

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 ...
3
votes
1answer
78 views

Proof that Grover's operator can be written as $D_N=-H_n R_N H_n$

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: $...
3
votes
1answer
68 views

Are there any other published quantum factoring algorithms that are simpler or more efficient than Shor’s?

How many qubits and what is the minimum number of gate operations needed to factor an n-bit integer? Are there any other published algorithms that are simpler or more efficient?
2
votes
1answer
42 views

Calculating entries of unitary transformation

Let $U$ be a unitary $n$-qubit transformation that applies a Hadamard on the $k$-th qubit and the identity on all the others. How would I go about calculating $U_{ij}=\langle i | U | j \rangle$ in ...
1
vote
1answer
41 views

Quantum transformation equivalent to Discrete Wavelet transform

Suppose we have a matrix $A=\begin{bmatrix} 2 &4 \\ 1 & 4\\ \end{bmatrix}$, when applying the discrete wavelet transform to this matrix we get 4 parts i.e smooth part ($1\times 1$) matrix, 3 ...
6
votes
2answers
163 views

Will quantum computers be able to solve the game of chess?

Will it be possible to use quantum computing to one day solve the game of chess? If so, any estimate as to how many qubits it would require? The game of checkers has already been solved through back ...
5
votes
2answers
137 views

Hidden shift problem as a benchmarking function

I encountered the hidden shift problem as a benchmarking function to test the quantum algorithm outlined in this paper (the problem also features here). There are two oracle functions $f$, $f'$ : $...
3
votes
0answers
62 views

Quantum addressing scheme

Nielsen explains how a search algorithm can access a classic database. I have a few questions. I hope you can help me a bit :) I work with a few quotes from the book. The principle of operation is ...
3
votes
0answers
41 views

What are applications of HHL's “simple example” to determine similar stable states of different quantum processes?

The HHL paper "Quantum algorithm for linear systems of equations" [link] initially describes a "simple example" to illustrate the potential power of their algorithm. They state: Consider a ...
5
votes
3answers
179 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 ...
7
votes
1answer
112 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
66 views

Reason for evaluating $a^x \bmod N$ from $x = 0$ to $N^2$

As per the Shor's algorithm, we need to evaluate $a^x \bmod N$ from $x = 0$ to $N^2$. What is the reason for this? Why can't we just evaluate for $N$, $2N$ or something like that?
3
votes
0answers
58 views

Genetic algorithm does not converge to exact solution

I'm trying to evolve quantum circuits using genetic algorithms as they did in this paper Decomposition of unitary matrices for finding quantum circuits: Application to molecular Hamiltonians (Daskin &...
7
votes
0answers
149 views

Is there a list of accessible open problems in quantum computing from a theoretical computer science perspective?

(Classical) theoretical computer science (TCS) has a number of outstanding open problems that can easily be instantiated in a manner that is accessible to a wider general public. For example, ...
3
votes
1answer
294 views

Grover's algorithm: number of searches

I would like to start my question with a quote: If an encrypted document and its source can be obtained, it is possible to attempt to find the 56-bit key. An exhaustive search by conventional means ...
4
votes
2answers
122 views

Constructing a circuit which performs the transformation $|x,y\rangle \to |x, x + y \bmod 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 ...
2
votes
1answer
46 views

Consequences of Grover's algorithm

I want to look more closely at the consequences of the Grovers algorithm. As is well known, the algorithm provides a quadratic improvement compared to classical search algorithms. Specifically, I ...
4
votes
2answers
62 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
2answers
51 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 ...
5
votes
1answer
80 views

Phase estimation algorithm: probability bound of obtaining $m$

Note: Cross-posted on Physics SE. Hi, I'm studying the quantum phase estimation algorithm from this book: M.A. Nielsen, I.L. Chuang, "Quantum Computation and Quantum Information", Cambridge Univ. ...
2
votes
1answer
67 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$ ...
0
votes
1answer
79 views

What can be a mini research project based on Grover's algorithm or the Deutsch Jozsa algorithm?

I need to work out a research project on quantum computing as a part of my curriculum. I was wondering how to implement something theoretically with the basic knowledge I have. I have learned about ...
9
votes
1answer
167 views

Why is an oracle qubit necessary in Grover's algorithm?

I am a bit confused about the necessity of an oracle qubit in Grover's algorithm. My question is, does it depend on how you implement your oracle whether you need an oracle qubit or not? Or, it there ...
3
votes
1answer
62 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
4answers
607 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 ...
8
votes
1answer
220 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 ...
5
votes
2answers
473 views

How to prove that the query oracle is unitary?

The query oracle: $O_{x}|i\rangle|b\rangle = |i\rangle|b \oplus x_{i}\rangle$ used in algorithms like Deutsch Jozsa is unitary. How do I prove it is unitary?
2
votes
3answers
127 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
68 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?
5
votes
0answers
195 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, ...
2
votes
1answer
45 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 ...
5
votes
1answer
69 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. ...
4
votes
1answer
61 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 ...
7
votes
2answers
557 views

Inner product of quantum states

I found an algorithm that can compute the distance of two quantum states. It is based on a subroutine known as swap test (a fidelity estimator or inner product of two state, btw I don't understand ...
2
votes
1answer
74 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
1answer
79 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
183 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 ...
9
votes
2answers
212 views

Composing multiple quantum circuits in single quantum program in QISKit

I was wondering if there is a way to compose a program with multiple quantum circuits without having the register reinitialized at $0$ for each circuit. Specifically, I would like run a second ...
1
vote
2answers
118 views

How can the state $\lvert0\rangle+M^{-1/2}\sum_{j=1}^M\lvert j\rangle$ be generated?

I was wondering if anybody to help me to generate the following state. It would be preferable if you use only Hadamard, CNOT and T-gates, on $\lceil\log_2(M+1)\rceil$ qubits: $$|\psi\rangle = \frac{1}{...