Skip to main content

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
1 answer
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 ...
Robert Singleton's user avatar
0 votes
1 answer
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 ...
Дмитрий Лапин's user avatar
1 vote
2 answers
64 views

Can non-linear operations be implemented as a circuit on a quantum computer?

Suppose I have a Quantum circuit, which gives an output state $|\psi \rangle$ let's say. I wish to obtain the reduced density matrix by tracing out subsystem B, i.e. $\rho = |\psi \rangle \langle \psi ...
Soumyadeep sarma's user avatar
-3 votes
1 answer
51 views

Is there any way to get an exponential speedup with quantum algorithm without quantum computer? [closed]

I am a student in Oxford University and I am studying a quantum computing? And my goal is to make a computer what can improve speed exponentially vs classical computer. Is there any way to get an ...
user30430's user avatar
-1 votes
0 answers
12 views

New Packages for complete_meas_cal and CompleteMeasFitter

I'm reading a code that uses the functions complete_meas_cal, CompleteMeasFitter to implement error mitigation (in Qiskit). However, these two functions are deprecated, and I couldn't find the updated ...
Yili's user avatar
  • 23
0 votes
0 answers
30 views

Explanation of quantum algorithm for numerical gradient estimation

My question concerns this algorithm: Fast Quantum Algorithm for Numerical Gradient Estimation by Stephen P Jordan https://arxiv.org/pdf/quant-ph/0405146 I am unable to understand this step of the ...
shashvat's user avatar
  • 807
0 votes
1 answer
28 views

Existence of FHE scheme that supports evaluation of obfuscated Quantum Functionalities

While reading this paper I came across the following text: A natural approach to obfuscation involves the notion of fully- homomorphic encryption (FHE), which allows for encoding data x into a ...
Qui Gonn Jinn's user avatar
0 votes
0 answers
31 views

Unitary retrieving game

My question is about the optimal strategies for retrieving/estimating an $n$-qubit black-box unitary $U$ using sequential single-shot measurements. Each shot is selected from a finite set of what I ...
trurl's user avatar
  • 131
1 vote
1 answer
32 views

Verifying block encoding by computing inner products

Assume that we know each matrix element $A_{ij}$ of a $n$-qubit matrix $A$, and we are given an $(n+m)$-qubit unitary $U_A$ that we would like to verify is a $(1,m)$-block encoding of $A$. To do this, ...
SescoMath's user avatar
  • 549
1 vote
2 answers
88 views

Hamiltonian Simulation: What's the meaning of t in $\exp(iAt)$?

My main goal is to find eigenvalues of some hamiltonian matrix $A$. When implementing Quantum Phase Estimation, I need to provide my circuit with informations about $A$. From what I have seen so far, ...
Max's user avatar
  • 13
0 votes
0 answers
22 views

Constructing amplitude oracle for complex-valued matrix

Let $a, b \in \mathbb R$ such that $\vert a + ib \vert < 1$. Does there exists a generic $2$-qubit unitary such that $$(a |0\rangle + \sqrt{1 - a^2}| 1 \rangle) \otimes (b|0\rangle + \sqrt{1 - b^2}|...
SescoMath's user avatar
  • 549
0 votes
0 answers
12 views

What is the measurement algorithm that the PyClifford's authors used?

I am studying how to perform measurements on pure stabilizer states of the Pyclifford package. The author used the convention to represent stabilizer states the same as in the paper: Improved ...
Việt Nguyễn's user avatar
2 votes
0 answers
38 views

Turning Deutsch-Josza into a continuous problem

I am wondering whether anyone has investigated if there is a notion of a continuous oracle. My starting off point is to consider the Deutsch-Josza problem, in which the oracle acts on the state in a ...
SescoMath's user avatar
  • 549
0 votes
1 answer
39 views

Unable to extract the quantum registers information from qiskit quantum circuit data

Consider the following code: ...
Vikram Dorbala's user avatar
6 votes
1 answer
226 views

What problems in chemistry or materials science could be solved with 100 fault-tolerant qubits?

Background IBM, Infleqtion, QuEra, and other quantum hardware companies have announced roadmaps where they expect to have 100 or more fault-tolerant qubits by the end of the decade. It seems ...
taciteloquence's user avatar
1 vote
0 answers
21 views

Can we use inverse transform sampling in probability loading process of quantum computing?

Recently, I read some papers about Quantum Monte Carlo (QMC), which can speed up the classical Monte Carlo quadratically. However, the efficiency of QMC largely depends on the probability loading ...
ddk's user avatar
  • 11
1 vote
0 answers
28 views

Experimental implementation of addition on a quantum computer

Addition is a basic arithmetic routine, but it has been surprisingly difficult to find a reference that experimentally implements it, despite it existing on various tutorials such as qiskit. Is there ...
shixian105's user avatar
2 votes
0 answers
64 views

Most relevant conference for Quantum Computing

I will have to supervise a PhD on Quantum Computing for Optimization problems. In this respect, I would like to attend to a conference on Quantum Computing, so as to get a clear view of the most ...
deb2014's user avatar
  • 181
1 vote
0 answers
9 views

Solving KnapSack problem on D Wave hybrid CQM

I am solving 01 KnapSack problem for 500k items with the help of hybrid CQM solver of D Wave. And for comparison I solved same problem with CPLEX. Solution quality of CPLEX solver is better than D-...
Maths_hawk's user avatar
1 vote
1 answer
74 views

Pauli Strings on the same qubit?

I am working on solving a Max-Cut problem using fewer qubits via efficient encoding methods of more classical information onto a single qubit.Using the method of The original problem has the ...
Another Random Guy's user avatar
3 votes
1 answer
118 views

What's the cost of finding $(x,y)$ such that $g(f(x),y)=1$ via Grover?

I have two functions $f:\{0,1\}^n \rightarrow \{0,1\}^m$ and $g: \{0,1\}^m \times \{0,1\}^k\rightarrow \{0,1\}$ and I want to find a point $(x,y)$ such that $g(f(x),y)=1$ (let's assume there is only ...
ivmihajlin's user avatar
2 votes
0 answers
23 views

Graph coloring optimization with quantum computing

I'm a computer science student at the University of Geneva, currently working on my bachelor thesis. My project involves conducting a significant optimization task on graph coloring using quantum ...
Leo Pellandini's user avatar
3 votes
3 answers
218 views

How to convert a combinatorial optimization problem into a problem hamiltonian

I want to ask how I can convert any combinatorial optimization problem into a Problem Hamiltonian, since such a conversion is needed in order to solve an optimization problem on quantum hardware (e.g. ...
Maths_hawk's user avatar
2 votes
1 answer
84 views

Does Qiskit SamplerV2 change circuit depth?

I'm currently implementing some algorithms on IBM quantum devices. After the migration to qiskit 1.0, I started using primitives and SamplerV2. What I observed is that even if I manually select a ...
G.Lebonwski's user avatar
0 votes
1 answer
52 views

How to draw a balanced function for three-bit input?

I am trying to think of how I can draw a balanced function for three-bit input using only 2 Toffolis, 3 CNOTs and 1 Inverter. Would this be even possible?
heheecskdeelmao's user avatar
2 votes
1 answer
65 views

List of references for quantum algorithms for optimization problems

I have to perform a bibliography review on all quantum algorithms available for mainly optimization problems, whether or not they can run now (NISQ) or at FTQC era. This review includes "pure&...
deb2014's user avatar
  • 181
1 vote
1 answer
60 views

How to correctly compute expectation value in QAOA?

In QAOA after prepating $|\psi(\gamma, \beta) \rangle$, expectation value $\langle \psi(\gamma, \beta)|H_c|\psi(\gamma, \beta) \rangle$ is computed. In tutorials, I see two approaches to this ...
Oleksii's user avatar
  • 21
3 votes
0 answers
40 views

Alternative algorithm for quantum phase estimation problem

The Quantum Phase estimation problem is stated below: Input: Given $U$ as a unitary operator acting on an m-qubit register. If $| \psi \rangle$ is an eigenvector of $U$, then U$| \psi\rangle$ = $e^{ ...
Manish Kumar's user avatar
1 vote
1 answer
68 views

Why does the QFT provide for so many controlled rotations?

I'm new to quantum and I wanted to understand why QFT uses controlled rotation gates. Thank you all
Azure's user avatar
  • 19
1 vote
0 answers
16 views

Why we do SWAP operations for applying a mode N function in Shor algorithms and How we do this swapping? [duplicate]

I am working on implementing shor algorithm for finding prime factors of N = 15. I am trying to understand a code of qiskit, but i am confused how and why the code editor is using swap codes to define ...
Tayyab Yahya's user avatar
0 votes
2 answers
82 views

What's the result of applying a CNOT gate followed by a Hadamard?

Say I have the following circuit And the input is $|\psi\rangle=\frac12(|00\rangle+|11\rangle+|01\rangle+|10\rangle)$. To find the output sate, I would first apply the CNOT to the second bit, ...
afebs's user avatar
  • 63
0 votes
1 answer
78 views

How to perform amplitude amplification to return $|\psi_{\rm good}⟩$ from $\cos\theta|\psi_{\rm good},\phi⟩+\sin\theta|\psi_{\rm bad},\phi^\perp⟩$?

You are given access to a quantum algorithm $A$ that prepares a state $$|\psi\rangle=cos\theta|\psi_{good}\rangle|\phi\rangle+sin\theta|\psi_{bad}\rangle|\phi^{\perp}\rangle$$ Where $|\phi\rangle=\...
afebs's user avatar
  • 63
5 votes
1 answer
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
Mathias Pichler's user avatar
3 votes
1 answer
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 ...
Another User's user avatar
4 votes
1 answer
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) ...
Thyrum's user avatar
  • 61
0 votes
0 answers
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 ...
afebs's user avatar
  • 63
2 votes
1 answer
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 ...
Manish Kumar's user avatar
1 vote
0 answers
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 ...
Moto's user avatar
  • 11
1 vote
1 answer
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....
Manish Kumar's user avatar
2 votes
1 answer
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 ...
qwerty's user avatar
  • 21
1 vote
2 answers
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 ...
tangyao's user avatar
  • 151
2 votes
1 answer
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 ...
Việt Nguyễn's user avatar
2 votes
0 answers
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 ...
Manish Kumar's user avatar
1 vote
0 answers
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 ...
Aman's user avatar
  • 503
2 votes
1 answer
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 ...
HelloMan's user avatar
  • 123
1 vote
0 answers
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 ...
Mihir Macwan's user avatar
2 votes
1 answer
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. ...
Martin Vesely's user avatar
3 votes
0 answers
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 ...
Featherball's user avatar
5 votes
0 answers
70 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
2 votes
1 answer
49 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

1
2 3 4 5
25