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
0 votes
0 answers
20 views

Generating Equal Amplitude Superposition States from Another Equal Amplitude Superposition State

Can we prepare a state regarding a transformation in quantum computing that seems to generate another equal amplitude superposition state when applying a Hadamard gate? Specifically, I observed that ...
Aman's user avatar
  • 483
2 votes
1 answer
178 views

Classical computation required in Shor's algorithm: are they heavy?

A quantum computer also requires to perform classical computations. I would like to know if to implement Shor's algorithm, there is a heavy classical computation cost (i.e. that would require a ...
HelloMan's user avatar
  • 123
1 vote
0 answers
8 views

Can dimensionality reduction be used to simplify data before using an optimization algorithm?

I am attempting to use a quantum algorithm, like a QAOA, to solve an optimization problem. I saw that qPCA can be used to simplify datasets and make them easier to analyze. Can quantum optimization be ...
Mihir Macwan's user avatar
2 votes
1 answer
96 views

Non-linear quantum mechanics and NP-complete problems

Thanks to user Cuhrazatee (comments to my other question here) I came accross article Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems by D. Abrams and S. ...
Martin Vesely's user avatar
3 votes
0 answers
29 views

How to create a quantum algorithm to determine unknown coefficients in a linear function

I am trying to solve the following practice question shown below. I am stuck on part (c) where I must design a quantum algorithm to solve the stated problem. I can tell that the solution is probably ...
Featherball's user avatar
5 votes
0 answers
49 views

Can we beat Grover for derangement problems?

Recall that a derangement of $N$ objects is (isomorphic to) a permutation of $\{1,\cdots, N\}$ that has no fixed point. The probability that a random permutation $f$ is a derangement rapidly reaches $\...
Mark Spinelli's user avatar
1 vote
1 answer
38 views

Complexity of controlled-$U^j$ operations in QPE applied to Hamiltonian simulation

One method to obtain the eigenvalues of a Hamiltonian $H$ is by applying quantum phase estimation to its time-evolution operator $U(t) = e^{-iHt}$. If I want to obtain an eigenvalue to $k$ bits in ...
Solarflare0's user avatar
0 votes
0 answers
34 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
49 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
62 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
41 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
45 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
152 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
37 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
88 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
250 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
  • 199
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
0 votes
1 answer
89 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
60 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
150 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
38 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
75 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
253 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
14 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
43 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
56 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
  • 881
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
155 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
158 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
606 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
  • 199
1 vote
1 answer
49 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
55 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
  • 199
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
  • 199
0 votes
1 answer
370 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
42 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
  • 881
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
108 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
125 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
181 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
238 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

1
2 3 4 5
24