Questions tagged [quantum-algorithms]

For questions about quantum algorithms, that is, sequences of quantum gates, operations, and measurements, whose purpose which achieve some goal. Standard examples are Shor's and Grover's algorithms.

Filter by
Sorted by
Tagged with
1 vote
0 answers
17 views

Proof that if W is the image of a Unitary operator with an $n^O(1)$ size quantum circuit, then $R_W$ has an $n^O(1)$ circuit as well

I have been working on the following problem Suppose $H$ is the Hilbert space of n qubits. Let $W_0$ be the subspace of $H ⊗ H$ with basis $|x_0⟩$, x = 0,...,N −1 where $N = 2^n$. Suppose $U$ is a ...
3 votes
2 answers
230 views

Prove that there is no polynomial size quantum algorithm for a Simon's problem with no promise on the input

We look at the following variant of Simon's problem. There is an algorithm $A$ that solves a problem with the following settings: The input is an oracle $f:\{0,1\}^n \to [M]$. The output of the ...
0 votes
0 answers
43 views

If someone handed you a fault tolerant quantum computer with, say 1 million logical qubits, what would be the first thing you would run? [closed]

A little survey here. Let us assume that all the hurdles of the NISQ era are surpassed and we have arrived to an era in which we have a fault tolerant quantum computer with a huge number (say a ...
1 vote
1 answer
59 views

How to calculate quantum cost?

In the following two papers: Automatic Synthesis of Reversible Logic Circuit Based on Genetic Algorithm Particle Swarm Optimization based Circuit Synthesis of Reversible Logic a comparison ...
0 votes
1 answer
324 views

ModuleNotFoundError: No module named 'qiskit.extensions'

Environment Qiskit Finance version: 0.5.0 Python version: Using the Qiskit Lab v1.0.0 Operating system: Windows 11 Hi, technically I am new to this quantum computing stuff. I see that an upgrade of ...
1 vote
0 answers
40 views

Is this quantum circuit design more prone to noise?

I am designing a quantum circuit which uses one qubit as the control of many $\text{CSWAP}$ operations. And then, this qubit will be measured. Will the result be more prone to noise since all the ...
3 votes
1 answer
668 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 ...
1 vote
0 answers
24 views

How to combine a VQE circuit with normal qiskit quantum circuit without parameters and give the measured set of qubits to the estimator?

I want to use a parameterized quantum-circuit which is $\text{CNOT}$ with another quantum-circuit that has no parameters, then after a series of gates on the second quantum-circuit, I want to measure ...
2 votes
0 answers
81 views

Approximating QFT using only sub-additivity and only $O(n\log n)$ quantum gates

In the original QFT, there are $O(n^2)$ quantum gates, and it looks like this: Where the controlled version of $R_k = \begin{pmatrix} 1 & 0\\ 0 & e^{\frac{2\pi k}{2^k}} \end{pmatrix}$ is used....
3 votes
2 answers
87 views

Time Complexity of Deustch Algorithm

The Deustch algorithm use an oracle, the quantum gate $U_f$ The first question is can we count the complexity of $U_f$ as one if it is used once. I mean since one computation of $U_f$ can't be ...
0 votes
1 answer
37 views

How is the oracle actually implemented for Deutsch-Jozsa algorithm? [duplicate]

In the quantum computation circuit for the Deutsch-Jozsa algorithm, it is said that $U_f$ oracle will affect certain specific operations on the qubits using $f(x)$ and finally will give the answer in ...
25 votes
5 answers
6k views

How would I implement the quantum oracle in Deutsch's algorithm?

I am trying to simulate Deutsch's algorithm (elementary case of Deutsch-Jozsa algorithm), and I am not entirely sure how I would go about implementing the quantum oracle necessary for the algorithm to ...
0 votes
1 answer
42 views

Full result of qiskit sampler

In Qiskit, I have a quantum circuit of 20 qubits. Hence the measurement result I am expecting is a dictionary of size 2^20. However, the quasi_dists from ...
4 votes
1 answer
603 views

Why is it not a good idea to run Shor's algorithm on a big noisy quantum computer?

Suppose I try to run Shor's algorithm on a big noisy quantum computer. For a given input I repeat the circuit many times and collect statistics for the measurements of each qubit. Now based on the ...
8 votes
1 answer
251 views

How to translate between continuous variable model and discrete model?

If I understand correctly, the discrete and continuous variable (CV) version of quantum computation are equivalent. However, the continuous aspect of the CV model makes me wonder to what extent can ...
1 vote
0 answers
42 views

working of Variable time amplitude amplification (VTAA) compared to amplitude amplification (AA)

I read the paper by Ambianis on variable time amplitude amplification to improve the $\kappa$ (condition number) dependency for the Quantum linear system algorithm by Childs et al.. I can see VTAA ...
3 votes
1 answer
150 views

Why is the coefficient-squared the probability, and not just the coefficient itself?

Context: I have decided not to accept the postulates of quantum mechanics blindly as gospel. There must be a way someone arrived at those postulates, and I want to know the basic reasoning behind them,...
2 votes
1 answer
36 views

How many oracles can satisfy a solution of Simons problem?

I know that the f/oracles in Simons algorithm is 2-1, and that $f(x)=f(y)\iff y=x\oplus s$. My question is if we can have gave different oracles/functions, that has the same codomain/output for a ...
1 vote
0 answers
44 views

What is the intuition behind achieving Quantum advantage in simulating non-hermitian dynamics using Quantum computer?

There have been several works on simulating ODE for classical systems like here and here. They are quantum techniques to solve the ODE related to classical systems. A generic methodology is: To solve ...
5 votes
1 answer
527 views

Quantum circuit for Szegedy quantum walk on a cyclic graph

I'm trying to implement an efficient circuit for the Szegedy quantum walk on a cyclic graph with number of nodes N = 8. I found the circuit in this thesis (page 39), the two images below show graph ...
0 votes
1 answer
87 views

What is the oracle in every quantum algorithm?

There is a machine called oracle which appears in a lot of algorithm of quantum computing, such as Deutsch's algorithm, QFT period-finding. This oracle machine really makes me confused. I've read ...
15 votes
4 answers
2k views

Are there any examples of anyone applying quantum algorithms to problems in computational biology?

As the title suggests, I'm searching for published examples of quantum algorithms being applied to problems in computational biology. Clearly the odds are high that practical examples don't exist (yet)...
3 votes
0 answers
58 views

Why FACTORING is in second level of Fourier hierarchy?

As per comlexityzoo web, the definition of the k-th level of Fourier Hierarchy (FH) is: $FH_k$ is the class of problems solvable by a uniform family of polynomial-size quantum circuits, with k levels ...
0 votes
1 answer
503 views

Kaye Exercise 6.4.2 Classical Deutsch-Jozsa algorithm

Can anyone help with this problem from, An Introduction to Quantum Computing, Phillip Kaye, Raymond Laflamme, Michele Mosca Exercise 6.4.2: Show that a probabilistic classical algorithm that makes $O(...
4 votes
1 answer
145 views

Requirement of vector 'b' in the definition of Phase Estimation Sampling (PES)

In this paper (last paragraph, page 3) by Wocjan and Zhang, the definition of PES requires vector/bit string b. The phase estimation problem (PE) very much inspires the definition. I cannot ...
5 votes
2 answers
547 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?
0 votes
1 answer
50 views

Can we train Parametric Quantum Circuits to map any probability distribution to Normal Distribution?

I am trying to find any references to train PQCs to map any probability distribution to a Normal Distribution. Suppose I have MNIST dataset, I want to apply PQC and make the readout distribution to be ...
2 votes
2 answers
248 views

TranspilerError: 'Number of qubits (40) in QAOA is greater than maximum (30) in the coupling_map'

Hi Ive been trying to solve a custom PO problem using QAOA and I ran into this particular error. As per my understanding,this is due to the limitation of the simulation hardware. But as per the ...
0 votes
0 answers
36 views

How to decompose a permutation matrix into two-level unitary matrices?

Assume a have a SBox and want to make quantum circuit for it. The unitary transform matrix for a SBox is special - a permutation matrix. I found an algorithm to decompose any unitary matrix into two-...
3 votes
1 answer
66 views

Understanding how to solve group isomorphism given the state $\sum_{\pi \in S_n} |\pi(G) \rangle$

Let $G=([n],E)$ be an undirected graph, which is represented by a $n \choose 2$ bit string, by indicating for each $i < j$ if $(i,j) \in E$. And let $| G \rangle$ be the $n \choose 2$ qubit state ...
1 vote
1 answer
74 views

What is wrong with my quantum grover's algorithm?

I am trying to create Grover's algorithm in quantum programming with Qiskit to find the target binary string 010. This is my process : Apply a Hadamard gate to 4 ...
13 votes
2 answers
2k views

Quantum algorithm for linear systems of equations (HHL09): Step 1 - Confusion regarding the usage of phase estimation algorithm

I have been trying to get my head around the famous(?) paper Quantum algorithm for linear systems of equations (Harrow, Hassidim & Lloyd, 2009) (more popularly known as the HHL09 algorithm paper) ...
2 votes
1 answer
46 views

Grover search - data representation

I am a mechanical engineer conducting an undergrad research project on quantum computing so fairly new to the whole thing, forgive me if this is a silly question. I understand the basic principles of ...
1 vote
0 answers
11 views

What is the benefit of using a Multi Angle QAOA?

I am currently doing some research that requires a quantum optimization algorithm. I have been looking at types of quantum algorithms to see which one would be most useful for my problem and ...
5 votes
2 answers
190 views

What is the shortest-circuit-depth quantum-benchmarking algorithm?

An algorithm implementing a model whose results are known, and from the known results, the benchmarking of the device could be done. What is the currently known shortest circuit depth algorithm that ...
43 votes
1 answer
2k 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 ...
-1 votes
1 answer
135 views

4-cities traveling salesman quantum algorithm (QUBO)

A quantum version of the traveling salesman algorithm is discussed here: There is a reference to QUBO, Ising, and some matrix constructions, and the output in the end: Is anyone able to run through ...
1 vote
0 answers
21 views

free complex amplitudes for qubits in Qiskit runtime

When I try to run circuits with initialize(),or StatePreparation(), I get ...
2 votes
1 answer
50 views

Do some Hamiltonian simulations require an irreversible process?

I just stumbled upon this research paper https://arxiv.org/abs/2309.16596. They claim to have found a problem which is easy to solve quantumly but hard classically: to find local minima of 2D ...
2 votes
1 answer
206 views

Implementing a Gaussian elimination solver for Simon's algorithm's outcome of linear equations

I'm trying to implement a gaussian elimination solver for the linear equations that are the outcome from simon's algorithm. I implemented two solutions, first: https://stackoverflow.com/a/45527097 ...
1 vote
0 answers
21 views

Implementing scalar multiple of a polynomial using quantum signal processing

Let $p(x)$ be a degree $d$ polynomial such that $|p(x)|\leq 1$ for $x \in [-1,1]$. Assume I have constructed a quantum circuit, $V(x)$, that implements $p(x)$ in the upper left entry of a $2$ by $2$ ...
3 votes
1 answer
149 views

How do I construct a circuit to reshuffle some computational basis vectors?

I would like to construct a quantum circuit s.t. It maps a certain (relatively small) subset of computational basis vectors onto a different subset of those, e.g. $$ |0101001\rangle \to |1000010\...
1 vote
1 answer
100 views

How to read the result of this HHL algorithm circuit output?

I have computed the final states of a 1-qubit HHL circuit using initial conditions $$ A|x\rangle = |b\rangle$$ $$\begin{bmatrix} 8 & 6+i \\ 6-i & -1\end{bmatrix} |x\rangle = \begin{bmatrix} \...
1 vote
1 answer
53 views

Question on efficiency of HOBO Quadratization and other depth reducing techniques

I am having trouble understanding some concepts in Quadratizing a high order polynomial. I am reading the review "Quadratization in Discrete Optimization and Quantum Mechanics" . I would ...
2 votes
0 answers
54 views

Modelling Mach-Zehnder and saturating Cramer-Rao bound

I am simulating (using Mathematica) a Mach-Zehnder interferometer, with photon counting measurements at the end (based on the setup described in the recent post) for the input state $|\psi\rangle:=|0,...
2 votes
2 answers
1k views

Can a quantum computer break a hash function?

I was watching this video by veritasium, https://www.youtube.com/watch?v=-UrdExQW0cs I'm curious on whether or not a quantum computer could break a hash function. I'm not really sure how hash ...
4 votes
3 answers
153 views

What is the definition of an "efficient" algorithm?

Suppose I have an algorithm that prepares a state of $N$ qubits ($N$ variable); I was recently told that the algorithm is called efficient if the depth of the circuit is independent of $N$. However, ...
5 votes
2 answers
245 views

How do you test a pair of unknown qubits for orthogonality with certainty?

If you want to check if a pair of unknown qubits are the same, a standard test is the controlled SWAP test. This gives a result of 0 with certainty if the states are the same and 1 with a 50% chance ...
1 vote
0 answers
12 views

How does QAOA choose its result from samples when there are degenerate states

When there are multiple samples corresponding to the same (minimum) energy and with the same probability, how does qiskit pick the final result? In my experiments, if I check all samples, I can see ...
1 vote
1 answer
56 views

About the formulation of an Ising Hamiltonian

I am reading the paper from Andrew Lucas, Ising formulations of many NP problems, and I am stuck with the formulation of the following Ising Hamiltonian: $$H = A \bigg( K - \sum_v x_v \bigg)^2 + B\...

1
2 3 4 5
24