Stack Exchange Network

Stack Exchange network consists of 174 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
0answers
9 views

Solution enumeration algorithm?

Suppose I have a quantum algorithm that produces, as solutions more than one different linear combinations with raised probability amplitudes. Each solution is correct in the context of this ...
1
vote
1answer
30 views

Multiple random coin flips without measurements

The question is similar to this one. As suggested in the answer, I can easily do this with just one qubit: I repeatedly Hadamard it and measure in order to have a fair coin flip at every point. The ...
4
votes
2answers
73 views

Grover's algorithm with W-state

In the general form of Grover's algorithm, we start with the uniform superposition of n qubits. Now, suppose instead that we start with a generic state, for example ...
2
votes
1answer
36 views

Understanding why the modular function part of Shor's algorithm is unitary

I've been struggling to understand the modular exponent bit of Shor's algorithm. My understanding is that it takes a register in the state $\frac{1}{\sqrt{Q}}\sum_{k=1}^{Q-1} |k\rangle |0\rangle$ to ...
1
vote
1answer
50 views

Building a matrix corresponding to the teleportation circuit

I'm trying to build the matrix that corresponds to this quantum teleportation circuit, but it never works when I test it in the quirk simulator, I tried finding the matrix corresponding to every part ...
4
votes
1answer
47 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$ ...
1
vote
1answer
49 views

Multiple random coin flips

Suppose that in my circuit I have to generate multiple, say n, random coin flips. For example, this coin flips could be used to activate ...
2
votes
0answers
20 views

Speedup Prange ISD using Grover

In his 2009 paper, Grover vs McElicee, Bernstein proposed to use the Grover's algorithm to obtain a quadratic speedup on the Prange ISD. However, it is not quite clear to me in which part of the ...
4
votes
2answers
69 views

How to get all combinations of given input?

I'm stuck with a very specific problem that I'm not sure on how to implement using quantum gates. Suppose I have an n qubit circuit and that I want in output a ...
2
votes
1answer
42 views

Why are these circuits not producing the same output?

I am simulating the phase shift algorithm on the Quirk platform. Even when the endian-ness of the built-in inverse QFT gate is corrected for, the circuits still output different results. Shouldn't the ...
7
votes
0answers
90 views

Quantum algorithms for problems outside NP

What is known about quatum algorithms for problems outside NP (eg NEXP-complete problems), both theoretically like upper & lower speedup bounds and various (im)possibility results, as well as ...
4
votes
1answer
46 views

Implementation of inverse QFT?

When implementing the inverse quantum Fourier transform, in addition to reversing the circuit, does one need to take the conjugate transpose of the phase shift gates in the circuit as well?
3
votes
1answer
28 views

Are the order finding and period finding algorithms the same thing?

Do they both just use similar methods of calculation, or are they completely interchangeable?
1
vote
1answer
30 views

Do these outputs seem normal for the order finding algorithm?

I'm sorry for posting so many questions about this specific problem, but I just want to make sure that I am implementing an algorithm correctly. I am simulating the order finding algorithm (finding ...
2
votes
1answer
31 views

Is this the correct quantum circuit for the order-finding algorithm?

The algorithm is being implemented on Cirq, with the goal of finding the smallest $r$ for cooprime numbers $x$ and $N$ satisfying the equation $x^r \ = \ 1($mod $N)$. I have set $x \ = \ 2$ and $N \ = ...
6
votes
1answer
95 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 $...
0
votes
2answers
85 views

How to prepare a superposed states of odd integers from $1$ to $\sqrt{N}$?

$\newcommand{\q}[2]{\langle #1 | #2 \rangle} \newcommand{\qr}[1]{|#1\rangle} \newcommand{\ql}[1]{\langle #1|} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\round}[1]{\left\lfloor #...
2
votes
0answers
62 views

Would this quantum algorithm implementation work?

I am trying to implement the order finding algorithm on Cirq finding the minimal positive $r$ for coprime $x$ and $N$ satisfying the equation $x^r \ = \ 1$(mod$ \ N$). In my case, I have set $x \ = \ ...
2
votes
1answer
85 views

An algorithm with the Hadamard operator

My goal in writing this algorithm in Q# was that func would either output (1,2) or (10,20), ...
4
votes
1answer
69 views

How to find parameters for circuit decomposition of Hamiltonian simulation of any matrix $A$?

In version 2 of the paper Quantum Circuit Design for Solving Linear Systems of Equations by Cao et al., they have given circuit decomposition for $e^{iA\frac{2\pi}{16}}$, given a particular $A_{4\...
4
votes
1answer
91 views

How to analyze highly entangled quantum circuits?

I came across a quantum circuit very similar to the phase estimation circuit, which is shown below: In the ...
0
votes
0answers
79 views

FPGA qubit simulation

This question is regarding the simulation of qubits, using FPGAs. My question is: how does using FPGAs to simulate qubits help us understand or give us an insight into how quantum computers could be ...
2
votes
0answers
42 views

Pointer to related research (paper)

Recently, I was reading a paper (arXiv:1804.03719 [cs.ET]), which had the following quote (the most relevant part has been bolded), Quantum algorithms are often grouped into number-theory-based, ...
5
votes
2answers
225 views

How to describe, or encode, the input vector x of Quantum Fourier Transform?

Firstly, I'd like to specify my goal: to know why QFT runs exponentially faster than classical FFT. I have read many tutorials about QFT (Quantum Fourier Transform), and this tutorial somehow explains ...
6
votes
2answers
117 views

Quantum Supremacy: How do we know that a better classical algorithm doesn't exist?

According to the Wikipedia (Which quotes this paper https://arxiv.org/abs/1203.5813 by Preskill) the definition of Quantum Supremacy is Quantum supremacy or quantum advantage is the potential ...
4
votes
1answer
51 views

Measuring the Hamiltonian in the VQE

I am trying to implement VQE in pyQuil and am dumbfounded by how to measure the expectation value of a general Hamiltonian on $\mathbb{C}^{2^n}$ i.e. determine $\langle\psi , H \psi\rangle$ on a ...
5
votes
2answers
96 views

Resources on hybrid quantum-classical algorithms applied to combinatorial optimization problems

I am doing a thesis on "Metaheuristics and Quantum Computing", and was wondering if anyone could recommend some papers/pages to read talking about hybrid quantum/classical computing. (My idea is to ...
3
votes
1answer
78 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 ...
5
votes
1answer
77 views

Is quantum backpropagation faster than classical backpropagation?

I recently stumbled upon a press release from Xanadu.ai stating that Under the hood, PennyLane's core feature is that it implements a version of the backpropagation algorithm - the workhorse for ...
6
votes
0answers
66 views

Shor's algorithm weaknesses & uniqueness of close rational

I'm working through a problem set, and am stuck on the following problem: a) What can go wrong in Shor’s algorithm if Q (the dimension of the Quantum Fourier Transform) is not taken to be ...
5
votes
1answer
106 views

What is the longest quantum circuit?

To date, what is the longest quantum computation ever performed? Length is measured in number of operations. EDIT --- I'm looking for a quantum computation with a clear ending and a clear output. ...
2
votes
0answers
78 views

Fastest quantum algorithm for numerical integration? [closed]

Question Let's say I have a system which one can use to compute an integral from $0$ to $X$ in time $2X$. Assuming it does so by taking time-steps $\epsilon$. What is the smallest time-step $\epsilon$...
5
votes
2answers
951 views

How is the Deutsch-Jozsa algorithm faster than classical for practical implementation?

There is something I really misunderstand about the Deutsch-Jozsa algorithm. To check if $f$ is balanced or constant, we use the following algorithm : Where $U_f$ gives $(x,y) \rightarrow (x, y \...
3
votes
0answers
53 views

Deutsch Algorithm on a Quantum Turing Machine

I understood how a Quantum Turing Machine works from this lecture. It would be great if someone could give an example of how this machine could be used to solve a real problem though, for example, ...
4
votes
1answer
93 views

Electronic structure calculations and the Ising model: practical?

I was reading this paper which introduces a mapping from a qubit Hamiltonian to an Ising model. Firstly, the first step of the mapping seems to assume that we know an eigenstate of the system (correct ...
9
votes
4answers
261 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 ...
4
votes
0answers
161 views

How can blackholes be fast information scramblers?

I noticed that there was already a post discussing the fast scrambling property of black holes. But it seems no satisfactory answer was given. As mentioned by L. Susskind et. al, the fast scrambling ...
3
votes
2answers
60 views

Unitary acting on standard qubit basis properties

If we have a $U$ (unitary with all real entries) such that: $U|0\rangle =a|0\rangle +b|1\rangle$ What is $U|1\rangle=?$ I know: the definition of what it means to be unitary ie. $U^\dagger U=UU^\...
1
vote
2answers
90 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}{...
8
votes
1answer
109 views

Quantum attack on hash functions

The line of questioning is inspired by the pick one trick in Section 4 of the PDF version of the paper Quantum Attacks on Classical Proof Systems - The Hardness of Quantum Rewinding (Ambainis et al., ...
4
votes
0answers
42 views

Why is there no $N$ in the time complexity of the QLSP algorithm by Childs et al.?

The paper Quantum linear systems algorithms: a primer by Dervovic et al has this table on page 3: I'm not sure why there's no $N$ in the time complexity of the algorithm by Childs et al. i.e. $\...
3
votes
1answer
62 views

Outcome of Hadamard transformation on a complex state

I would like to calculate the state after a transformation using the Hadamard gate on a complex state. I get stuck mid-calculation, most likely due to not being able to dealing with the global state. ...
6
votes
0answers
67 views

Does the GLOA have any advantage over the Solovay-Kitaev algorithm?

The Solvay Kitaev algorithm was discovered long before the Group Leaders Optimization algorithm and it has some nice theoretical properties. As far as I understand, both have exactly the same goals: ...
2
votes
0answers
43 views

Why does Fourier sampling allow to efficiently recover hidden subgroups?

The hidden subgroup problem is often cited as a generalisation of many problems for which efficient quantum algorithms are known, such as factoring/period finding, the discrete logarithm problem, and ...
4
votes
2answers
78 views

Do the probability amplitudes of the superposition state produced by the QFT transform convey useful information?

I have been studying on Quantum Fourier Transform (QFT) by myself, and I am little bit confused about how could QFT be used. For example, if the QFT of three quantum bits is $a_1|000\rangle + ...
4
votes
3answers
162 views

Quantum Computing Project

I am currently working on a quantum computing subject for my coding school, and I had some questions for you. My objective would be to introduce students to Quantum Computing with an algorithmic ...
5
votes
1answer
62 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 ...
6
votes
3answers
73 views

$R_z$ gate representations

Why is the $R_z$ gate sometimes written as: $$ R_{z}\left(\theta\right)=\begin{pmatrix}1 & 0\\ 0 & e^{i\theta} \end{pmatrix}, $$ while other times it is written as: $$ R_{z}\left(\theta\...
2
votes
0answers
52 views

Simulating Read only QRAM (constructing an oracle) [closed]

In many algorithms an array that stores a classical data or quantum data is crucial. The QRAM (quantum random access memory) that stores classical data in the circuit has been done. My question ...
6
votes
0answers
58 views

How significant are the variants of Grover's Algorithm?

I found a paper by Grover titled "How significant are the known collision and element distinctness quantum algorithms?", in which he expressed criticism to several famous algorithms, including ...