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.

3
votes
0answers
32 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 ...
1
vote
2answers
60 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 ...
3
votes
0answers
49 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?
4
votes
1answer
74 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
380 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
329 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
90 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: ...
4
votes
0answers
67 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 ...
2
votes
1answer
53 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). ...
8
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 ...
12
votes
2answers
652 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 ...
24
votes
2answers
1k views

How is the oracle in Grover's search algorithm implemented?

Grover's search algorithm provides a provable quadratic speed-up for unsorted database search. The algorithm is usually expressed by the following quantum circuit: In most representations, a crucial ...
7
votes
2answers
635 views

How can I calculate the inner product of two quantum registers of different sizes?

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

Understanding the oracle in Deutsch's algorithm

I am reading John Watrous' notes from his course CPSC 519 on quantum computing. In a pre-discussion before presenting Deutsch's algorithm to determine whether a function is constant or not, the author ...
2
votes
1answer
68 views

What happens in Deutsch algorithm if I use 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 ...
2
votes
1answer
69 views

Lesser qubit computer doing the parts of Shor's against e.g., RSA-2048 sized prime

After posting this question to Physics, it became pretty clear I should have posted here. So: How might a (e.g.) 72-bit crypto-relevant quantum computer attack RSA-2048? Bonus: how might that be ...
5
votes
3answers
248 views

Example of Hamiltonian Simulation solving interesting problem?

Hamiltionian Simulation (= simulation of quantum mechanical systems) is claimed to be one of the most promising applications of a quantum computer in the future. One of the earliest – and most ...
5
votes
1answer
163 views

Implementation of quantum adder

I'm looking at this paper and try to implement the Quantum adders they define myself. Suppose we have a number $b=b_{n-1}\dots b_1b_0$ and they want to add a constant number $a=a_{n-1}\dots a_1a_0$. ...
9
votes
3answers
206 views

General construction of $W_n$-state

Two of the most well known entangled states are the GHZ-state $|\psi\rangle = 1/\sqrt{2}\left( |0\rangle^{\otimes n} + |1\rangle^{\otimes n}\right)$ and the $W_n$-state, with $W_3 = 1/\sqrt{3}\left(|...
3
votes
0answers
41 views

Is HHL executed in a single run? If yes, how do they carry out controlled rotation without knowing eigenvalues?

Even after reading several papers and almost all HHL related questions and answers here on Quantum Computing Stack Exchange, one thing is yet not clear. In several papers, for illustrating HHL they ...
5
votes
1answer
102 views

Expected repetitions of the quantum part of Shor's algorithm

Shor's algorithm to factor a number $N$ goes as follows: Pick a random value $b \in (0, N)$. Use a specific quantum computation to a sample a value $v$ that should be close to $2^{m} k/p$ where $m$ ...
6
votes
1answer
234 views

Qutrit Teleportation

I'm working through Scott Aaronson's Quantum Information Science problem sets, and I'm having trouble with a specific problem in ps5 (PDF). Specifically the following problem: A “qutrit” has the ...
2
votes
1answer
26 views

How to pick number of simulation qubits for finding eigenvalue of fermionic Hamiltonian?

I am having some trouble understanding how the number of simulation qubits are chosen when finding the eigenvalue of a fermionic Hamiltonian. For the phase-estimation algorithm, is the number of ...
13
votes
2answers
513 views

What could be the possible future applications for HHL algorithm?

Note on the vocabulary: the word "hamiltonian" is used in this question to speak about hermitian matrices. The HHL algorithm seems to be an active subject of research in the field of quantum ...
10
votes
3answers
192 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?
-1
votes
1answer
109 views

Large size of matrices for little outcome [closed]

I am stuck in a dilemma about how to proceed with a quantum computing algorithm that changes the original state of a system to another. Say I have a superposition of all $8$ bit integer values that ...
0
votes
1answer
70 views

Grover's algorithm and RSA from Nielsen

Nilsen states that one can define a function for the oracle in the Grover algorithm, which is constructed as follows. So there is a number $m$ that consists of $p$ and $q$ (both primes) $m = pq$. Now ...
4
votes
2answers
79 views

Calculating the expectation value of a unitary operator on a quantum computer

What is the smartest way of calculating the expectation value of some unitary $U$ in some state $|\psi\rangle$? There are two ways I know: quantum phase estimation algorithm; Hadamard test. Are ...
2
votes
1answer
62 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 ...
6
votes
0answers
45 views

Are non-secret-based quantum money mini-schemes susceptable to Jogenfors' “reuse attack?”

Aaronson and Christiano call public-key or private-key quantum mini-schemes $\mathcal M$ secret-based if a mint works by first uniformly generating a secret random classical strings $r$, and then ...
2
votes
1answer
42 views

Amplitude Estimation Algorithm — Lambda (Q) Operator

I'm working on an implementation of the algorithms described Brassard et al. in the following paper: arXiv:quant-ph/0005055v1. I managed to make the amplitude amplification cases working but I'm ...
3
votes
1answer
88 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?
3
votes
1answer
70 views

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

My understanding of the Bernstein-Vazirani algorithm is as follows: We have a black box oracle with secret string $s$. The black box does $$f(x) =s\cdot{x}=(\sum_1^n s_i\cdot{x_i})$$ We run each ...
6
votes
1answer
165 views

Efficiently performing controlled rotations in HHL

This question builds off of this question. In the HHL algorithm, how do you efficiently do the $\tilde{\lambda}_k$-controlled rotations on the ancilla qubit? It seems to me that since you don't know ...
4
votes
0answers
81 views

Does HHL implementation require a priori eigendecomposition?

I am interested in HHL algorithm and despite all the problems related to current technologies, I am trying to understand how it has to be implemented. I have seen from these two available circuits (...
3
votes
0answers
48 views

Counting in Q#: number of solutions

I have this program derived from Microsoft Quantum Katas for counting (see here): ...
4
votes
0answers
108 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
164 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
48 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
99 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
57 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
75 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
243 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
107 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
92 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{,} $$...
4
votes
0answers
109 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
135 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
86 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: $...
2
votes
1answer
54 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
46 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 ...