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.

1,168 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
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 ...
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
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 ...
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
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 ...
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
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 ...
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....
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 ...
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 ...
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 ...
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 ...
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 ...
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
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 ...
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,...
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
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 ...
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 ...
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 ...
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)...
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 ...
503 views

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 ...
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, ...
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
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\...