# 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 ...
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 ...
• 101
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 ...
• 11
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
• 95
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 ...
• 209
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 ...
• 460
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....
• 209
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 ...
• 95
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 ...
• 460
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 ...
• 460
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-...
• 83
1 vote
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 ...
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 ...
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 ...
1 vote
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 ...
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 ...
• 21
1 vote
21 views

### free complex amplitudes for qubits in Qiskit runtime

When I try to run circuits with initialize(),or StatePreparation(), I get ...
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 ...
• 21
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 ...
• 460
1 vote
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$ ...
• 191
54 views

105 views

### Optimal dependency of HHL (or any QLSP) algorithm on condition number $\kappa$

This is conserning the optimal dependency on condition number for Quantum linear system problem (QLSP). For solving QLSP, the HHL (algorithm) paper mentions any polylog($\kappa$) quantum algorihm ...
• 460
123 views

### Quantum Phase Estimation answers distribution

Suppose I have a random unitary matrix, known eigenvectors and eigenvalues. I know that exact eigenvalue for the given matrix is $0.5491617699847768+0.835716070437315j$. From here, if I'm not mistaken ...
177 views

### Anything in between quadratic and exponential speedups?

Question There exist a handful of proven quadratic quantum speedups (some examples include [1-3]) and even a few proven exponential quantum speedups (some examples include [4-6]). But there seems to ...
• 1,756
231 views

### Is the $\mathcal O(n^2)$ cost of the quantum Fourier transform (QFT) known to be optimal?

The (classical) lower bound on Fast Fourier transform is still open question. The complexity of $\mathcal{O}(N\log(N))$ (due to Cooley-Tukey) is not known to be optimal. (Here, $N$ is the vector size.)...
• 460
75 views

### How does the complexity of extracting eigenvalues via quantum phase estimation compare with the classical one?

Suppose, I have ideal quantum computer that allows me to find exact eigenvalues with QPE algorithm under perfect matrix, eigenvectors and eigenvalues conditions. How the complexity of this algorithm ...
1 vote
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 ...
61 views

### confusion on the LCU method regarding the normalization

Let $A = \sum_{k} a_k U_k$ where $a_k$ are real, positive coefficients $U_k$ are unitary matrices. I have realized that $\sigma = A \rho A$ can be implemented on a quantum computer by using the LCU ...
• 169
31 views

### How to amplify amplitudes above some threshold, given additional information about the state

Given a quantum state $\left|\Psi\right> = \sum_{i=0}^{2^n-1} \alpha_i\left|i \right>$, for which I know that the probabilities ($|\alpha_i|^2$) follow a sine/cosine like distribution as in the ...
• 3
### How can I use Quantum Shanon Decomposition for any $N \times N$ matrix?
I have a non-unitary and non-hermitian matrix of $16\times16$. I have used singular value decomposition to break that matrix into three matrices i.e. $A = UDV$, Where $U$ and $V$ are unitary but still ...