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,214 questions
Filter by
Sorted by
Tagged with
1 vote
31 views

General number of classical bits: recycles qubits

I am trying to write a Qiskit routine to perform qubit recycling for Shor's algorithm. This is a procedure by which the M-bit control register is replaced by a single quantum register, and the ...
37 views

Problem with understanding advantage of QAOA over bruteforce

I am trying to figure out with QAOA alghorithm. I use the example from this qiskit notebook https://github.com/Qiskit/textbook/blob/main/notebooks/ch-applications/qaoa.ipynb. I have the question to ...
1 vote
64 views

• 63
530 views

How to read the result of quantum shor circuit for N=15

I found many circuits for the Shor algorithm for N=15, but i don't understand how to read the result 3 or 5. Where can i find the result e.g. for this circuit I found it here
47 views

What is the "equivalent" quantum computational complexity class of the classical class APX (or PTAS)?

According to Wikipedia, APX contains those optimization problems in NP for which there exists a polynomial time algorithm which approximates the objective function multiplicatively to within a ...
• 131
42 views

Simulating any fixed time classical circuit in time poly(t) on a quantum computer

I'm analyzing the paper "Quantum walk algorithm for element distinctness" by Ambainis and at the bottom of page 24 (the last line of "Additional requirements" in section 6.2) ...
• 61
116 views

An Introduction to Quantum Computing Exercise 7.1.6

This question is from An Introduction to Quantum Computing Kaye et al. I'm having a difficult time coming up with a solution for this question. It is in relation to period finding however I cannot ...
• 63
83 views

What is the promise gap in APPROX-CIRCUIT-VALUE (BQP-complete) problem?

I want to understand how the precision of promise gap on input size changes the problem's difficulty. I read the guided local Hamiltonian problem (GLHP). Description of GLHP: We have been given a ...
• 681
1 vote
18 views

Implementation of identity block initialisation strategy for mitigating barren plateaus

I have been trying to implement this paper on identity block initialisation strategy for barren plateau mitigation but I don't really understand how one would apply it to a parameterised circuit with ...
• 11
1 vote
74 views

On the genesis of 'APPROX-QCIRCUIT-PROB': a (promise) BQP-complete problem

Wikipedia mentions APPROX-QCIRCUIT-PROB (AQP) as a (promise) BQP-complete problem. It seems convincing that it is a complete problem for BQP. The lecture notes of Prof. Henry Yuen mention it too, here....
• 681
108 views

What are classical analogies for the notions of superposition, entanglement, and interference?

I'm working on a conceptual explanation of quantum computing properties and have used analogies to make the ideas more accessible. I'd appreciate feedback on the validity of these analogies from those ...
• 21
1 vote
104 views

What are the ambient group $G$ and the hidden subgroup $H$ in Shor's order finding algorithm?

It is widely believed that Shor's order-finding algorithm is an example of hidden subgroup problem. However, there is a little trick here. The problem is what is the hidden subgroup in Shor's order ...
• 151
114 views

Is $\rho = \sum_{j} p_j|n_j\rangle\langle n_j|$ a valid construction for any mixed state?

I have a mixed state $\rho$ and its hamiltonian $H$. Firstly, I find the eigenvalues $\{p_j\}$ of $\rho$, and orthonormal basis of $H$. I write $\rho$ in terms of $H$'s eigenstates and $\rho$'s ...
80 views

Is BQP contained in BPP with Quantum Phase Estimation (QPE) oracle?

I am trying to see if the below proposition holds: Proposition-1: $BQP\subseteq BPP^{QPE}$. Here, QPE is the Quantum Phase estimation algorithm. QPE takes an eigenstate and the unitary matrix as ...
• 681
1 vote
73 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 ...
• 503
204 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 ...
• 123
1 vote
16 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 ...
118 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. ...
• 14.6k
37 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 ...
• 131