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.

3
votes
1answer
46 views

Intuitive Proof: $\mathsf{BQP}\subseteq \mathsf{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 ...
4
votes
0answers
31 views

What is recursive Fourier sampling and how does it prove separations between $\mathsf{BQP}$ and $\mathsf{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
36 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
46 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
49 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?
5
votes
0answers
38 views

Correspondence between the Topological model and Quantum Circuit model

For example, given the $R$ & $F$ gates and Toric codes for a given problem, how to convert this code into the conventional circuit model and vice versa. From the literature developed, it seems ...
4
votes
1answer
68 views

Shor's algorithm effectiveness

In Shor's algorithm we require the period to be even. If the period is not even or $x^{r/2}+1 \equiv 0 \bmod N$ then we have to restart the process and pick a new random $x$. Why do we know that the ...
1
vote
1answer
33 views

Entanglement in VQE ansatz in Qiskit

The Qiskit documentation on VQE describes two of the ansatz as "rotations with entanglements". The rotation gates are more or less clear, but the documentation doesn't mention what gate is used for ...
3
votes
3answers
87 views

Classical complexity for Simon's problem

Simon's problem is that you are given a function $f : \{0,1\}^n \to \{0,1\}^n$ such that $f(x)=f(y)$ if and only if $x \bigoplus y$ is either $0^n$ or some unknown $s$. The problem is to find $s$. If $...
2
votes
3answers
2k views

Is there any (really) quantum procedure that's an algorithm and not a Las Vegas algorithm?

Let me take Grover's algorithm as an example. In most cases, Grover's algorithm is able to yield with a high probability the desired term of the superposition. When the superposition has more than 4 ...
2
votes
2answers
388 views

Shor's algorithm beginning

This may be a silly question but at the start of Shor's algorithm to factorise a number $N$ we need to find a number $n$ such that $N^{2} \leq 2^{n} \leq 2N^{2}$ Why does such a number $n$ exist for ...
5
votes
2answers
229 views

Why it is hard to simulate a quantum device by a classical devices?

I was recently watching a talk by Urmila Mahadev on "Classical Verification of Quantum Computations" (see this). I am not new to quantum computation just have a familiarity with the qubit and some ...
4
votes
1answer
35 views

Solution enumeration algorithm?

Suppose I have a quantum algorithm that produces solutions where more than one different linear combination of qubit values with raised probability amplitudes is a correct result. Each linear ...
1
vote
1answer
46 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
84 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 ...
4
votes
1answer
68 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
56 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 ...
5
votes
1answer
59 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
52 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
72 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
45 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
95 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
53 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
29 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
31 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
34 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
102 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
1answer
90 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
66 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
88 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
74 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
97 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
46 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
229 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
120 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
2answers
78 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
105 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
82 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
85 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
75 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
107 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
79 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
961 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
56 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
98 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
310 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
62 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^\...