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 ...
user145282's user avatar
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 ...
Nuno's user avatar
  • 101
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 ...
Dona's user avatar
  • 11
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 ...
Deren  Liu's user avatar
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 ...
K S Mallesh's user avatar
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 ...
Deren  Liu's user avatar
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 ...
Syed Shahmir Kazmi's user avatar
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,...
Abhay Agarwal's user avatar
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 ...
Pink Elephants's user avatar
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 ...
tangyao's user avatar
  • 95
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 ...
Gabi G's user avatar
  • 209
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 ...
Manish Kumar's user avatar
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....
Gabi G's user avatar
  • 209
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 ...
tangyao's user avatar
  • 95
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 ...
Manish Kumar's user avatar
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 ...
Manish Kumar's user avatar
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-...
Huy By's user avatar
  • 83
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 ...
Royal Mail's user avatar
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 ...
Lasal Hettiarachchi's user avatar
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 ...
Kasi Jaswin's user avatar
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 ...
Mihir Macwan's user avatar
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 ...
Max's user avatar
  • 21
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 ...
Deren  Liu's user avatar
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 ...
Matteo's user avatar
  • 21
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 ...
Manish Kumar's user avatar
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$ ...
user82261's user avatar
  • 191
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,...
John Doe's user avatar
  • 841
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 ...
Justin's user avatar
  • 11
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\...
Laura's user avatar
  • 59
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, ...
David Raveh's user avatar
2 votes
1 answer
150 views

Qiskit Runtime forbids reset gate?

Some parts of my quantum circuit uses initialize to prepare specific amplitudes to the qubits. However, the Qiskit Runtime outputs error: ...
Deren  Liu's user avatar
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 ...
Frederik Ravn Klausen's user avatar
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 ...
Gabi G's user avatar
  • 209
1 vote
1 answer
48 views

Pennylane and Qutrit quantum circuit matrix representation bug

I want to find the operator that describes this qutrit quantum circuit. Where a TSub, some TRZ rotations and a TAdd are applied to 2 quitrits. I am using Pennylane 0.34.0. This is the code: ...
Daniele Trisciani's user avatar
3 votes
1 answer
54 views

How can a third party learn the coefficient of a shared $2n$-qubits state using a classical message from each one?

Suppose Alice and Bob share the $2n$-qubits state $$|\phi _{x,y,b} \rangle = \frac{1}{2}(|x\rangle + (-1)^b |y\rangle)$$ where $x,y$ are $2n$-length strings of $0$ and $1$, $b$ is a bit, and $x \ne y$....
Gabi G's user avatar
  • 209
0 votes
1 answer
31 views

Parallelism of two or more quantum machines

Suppose I have 2 quantum machines: The first is 2 qubits machine and the second is 4 qubits. Is there a way to parallelize these machines and get a result as if I had 6 quibts machine? Is there a ...
Avi's user avatar
  • 153
0 votes
0 answers
48 views

Pseudo telepathy with 3 people that share the state $\frac{1}{2}(|000\rangle -|011\rangle-|101\rangle-|110\rangle)$

The problem is similar to the pseudo-telepathy where Alice, Bob and Charlie are given bits $a,b,c \in \{0,1\}$ such that $a \oplus b \oplus c=0$, and their goal is to output the bits $A,B,C$ without ...
Gabi G's user avatar
  • 209
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 ...
Ricardo Olvera Ramìrez's user avatar
1 vote
1 answer
39 views

Two-photon N00N state through Mach-Zehnder interferometer

I am interested in modelling a two-photon N00N state sent through a Mach-Zehnder interferometer, which consists of a beam-splitter (50:50), a phase shift operator on the first mode, a phase shift ...
John Doe's user avatar
  • 841
1 vote
1 answer
97 views

Algorithm to reveal properties of a random quantum permutation gate

Given a unitary $U$, which implements a random permutation $\sigma$, such that the input to the unitary permutes as here: $|v_1\rangle\otimes\ldots\otimes|v_n\rangle$ becomes $|v_{\sigma(1)}\rangle\...
schmector's user avatar
4 votes
1 answer
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 ...
Manish Kumar's user avatar
0 votes
1 answer
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 ...
Марина Лисниченко's user avatar
6 votes
1 answer
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 ...
sheesymcdeezy's user avatar
5 votes
2 answers
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.)...
Manish Kumar's user avatar
3 votes
1 answer
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 ...
Марина Лисниченко's user avatar
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 ...
QuantumTheoretical's user avatar
4 votes
1 answer
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 ...
Hailey Han's user avatar
0 votes
0 answers
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 ...
D.D.'s user avatar
  • 3
0 votes
1 answer
94 views

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 ...
Syed Shahmir Kazmi's user avatar
0 votes
0 answers
21 views

Is critical path/gate exist in quantum computation?

In a quantum algorithm, are there any quantum gates more important than the other gates? For example, if the same error happens to two H gates in a circuit, can we determine which gate has a larger ...
Amanli's user avatar
  • 35

1
2 3 4 5
24