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.

248 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9 votes
0 answers
420 views

Is there a BQP algorithm for each level of the polynomial hierarchy PH?

This question is inspired by thinking about quantum computing power with respect to games, such as chess/checkers/other toy games. Games fit naturally into the polynomial hierarchy $\mathrm{PH}$; I'm ...
Mark Spinelli's user avatar
8 votes
0 answers
192 views

Better "In-Place" Amplification of QMA

$\def\braket#1#2{\langle#1|#2\rangle}\def\bra#1{\langle#1|}\def\ket#1{|#1\rangle}$ In MW05 the authors demonstrate so-called "in-place" amplitude amplification for QMA, exhibiting a method for Arthur ...
bean's user avatar
  • 331
8 votes
0 answers
93 views

Are non-secret-based quantum money mini-schemes susceptable to Jogenfors' "reuse attack?"

Aaronson and Christiano call public-key or private-key quantum mini-schemes $\mathcal M$ secret-based if a mint works by first uniformly generating a secret random classical strings $r$, and then ...
Mark Spinelli's user avatar
8 votes
1 answer
634 views

Gradient boosting akin to XGBoost using a quantum device

I am currently trying to implement a boosting algorithm akin to XGBoost with a quantum device. The reason is that I want to make use of a quantum device to train weak classifiers. However, as far as I ...
QuanFinance's user avatar
8 votes
0 answers
364 views

Requirements for Achieving a Quantum Speedup

We usually talk about the power of a quantum computer by examining the separation between sets of gates that we know we can efficiently simulate on a classical computer (i.e. problems in the class BPP)...
DaftWullie's user avatar
  • 59.4k
7 votes
0 answers
73 views

Is there a practical architecture-independent benchmark suitable for adversarial proof of quantum supremacy?

Recent quantum supremacy claims rely, among other things, on extrapolation, which motivates the question in the title, where the word "adversarial" is added to exclude such extrapolation-...
fiktor's user avatar
  • 326
7 votes
0 answers
104 views

How to decide which quantum device to use if a quantum algorithm is given?

I'm planning to write my master thesis in quantum computing. The subject of the thesis is to find out which attributes (properties, features) of quantum algorithms respectively their implementations (...
krsp's user avatar
  • 79
7 votes
0 answers
75 views

If we could only get two-qubit tomography as an output, what algorithms are possible

According to the circuit model, the output for a quantum computation on $n$ qubits is an $n$-bit string. But what if we instead got a full two qubit tomography for all $n(n-1)$ pairs of qubits? This ...
James Wootton's user avatar
7 votes
0 answers
257 views

How can blackholes be fast information scramblers?

I noticed that there was already a post discussing the fast scrambling property of black holes. But it seems no satisfactory answer was given. As mentioned by L. Susskind et. al, the fast scrambling ...
XXDD's user avatar
  • 333
6 votes
0 answers
78 views

Is amplitude estimation optimal?

Amplitude estimation requires $O(1/\epsilon)$ measurements if we want to estimate an amplitude to absolute precision $\epsilon$. Is this optimal? Why can't we do better than this? I'm trying to see if ...
confusion's user avatar
  • 155
6 votes
0 answers
142 views

Weak Schur sampling and state distinguishability

Consider the task of distinguishing between the following two $n$ qubit quantum states. $$ \rho = \frac{\mathbb{I}}{2^{n}}.$$ $$ \sigma = \frac{1}{2^{n/2}}\sum_{x \in \{0, 1\}^{n/2}} |x\rangle\langle ...
BlackHat18's user avatar
  • 1,363
6 votes
0 answers
93 views

Postselection and hardness of estimating amplitudes

Let $A$ be a class of quantum circuits such that \begin{equation} \text{Post}A = \text{Post}BQP, \end{equation} where $\text{Post}$ indicates post-selection. Is only this amount of information ...
BlackHat18's user avatar
  • 1,363
6 votes
0 answers
145 views

What are quantum inspired algorithms?

I am starting to see press about quantum inspired algorithms. Are these algorithms that solve problems faster by looking at things from a quantum computing perspective?
LeWoody's user avatar
  • 854
6 votes
0 answers
159 views

How many qubits and how many gates, are required for finding the eigenvalues of a matrix?

Say I have an $N \times N$ matrix and I want to know the eigenvalues to a precision of $\pm \epsilon$. How many qubits and how many gates do I need?
Pablo LiManni's user avatar
6 votes
0 answers
149 views

How exactly is the stated composite state of the two registers being produced using the $R_{zz}$ controlled rotations?

This is a sequel to How are two different registers being used as "control"? I found the following quantum circuit given in Fig 5 (page 6) of the same paper i.e. Quantum Circuit Design for ...
Sanchayan Dutta's user avatar
5 votes
0 answers
72 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
5 votes
0 answers
120 views

Quantum Representation of the Brouwer problem

Brouwer’s fixpoint theorem guarantees a point, $x_0$, such that $f(x_0)=x_0$ for any continuous $f$ that maps a simplex (N dimensional triangle) to itself. In his presentation of the PPAD complexity ...
Steven's user avatar
  • 51
5 votes
0 answers
134 views

Why is lattice-based cryptography believed to be hard to solve for quantum computers?

Lattice-based cryptography is said to be the main contender for a post-quantum cryptography framework. It's thought that instead of having to switch everything over to QKD, post-quantum algorithms can ...
Steven Sagona's user avatar
5 votes
2 answers
191 views

What is the shortest-circuit-depth quantum-benchmarking algorithm?

An algorithm implementing a model whose results are known, and from the known results, the benchmarking of the device could be done. What is the currently known shortest circuit depth algorithm that ...
quantum's user avatar
  • 585
5 votes
0 answers
263 views

How to write the classical algorithm for lights out problem?

I am very new to quantum computing and I have started learning the concepts watching the IBM summerschool videos and trying to solve the IBM quantum challenge problems. One of their problems is ...
Delaram Nematollahi's user avatar
5 votes
0 answers
135 views

Computing the expectation values of a Hamiltonian constructed from a cost functions in combinatorial optimization

One of the main steps in Hybrid Quantum algorithms for solving Combinatorial Optimization problems is the calculation of the expected value of a hermitian operator $H = \sum{H_i}$ (where $H_i$ are ...
César Leonardo Clemente López's user avatar
5 votes
0 answers
101 views

Active areas of research for NISQ algorithms

What areas of research in NISQ algorithms have heavy focus? I'm interested in quantum chemistry algorithms because of previous work (e.g. VQEs), and I'd love to learn more about other near-term ...
C. Kang's user avatar
  • 1,754
5 votes
0 answers
250 views

Could quantum computing help solving the Eternity II puzzle?

First of all, since I am not a specialist, sorry if this question does not make sense. But, I can't resist to ask as I have not found any direct information while googling. I hope some of you know/...
Patrice's user avatar
  • 83
5 votes
0 answers
72 views

Max eigenvalue algorithm via annealing starting from Gibbs state

In this talk, and the corresponding slides on page 24/44, Brandao talks about the max eigenvalue problem which is: Given a Hermitian $n\times n$ matrix $H$, approximate its largest eigenvalue. (Note ...
Marsl's user avatar
  • 949
5 votes
0 answers
159 views

Exact functions of a single-iteration Grover Search Algorithm's operators

I'm doing a practice assignment where I'm asked to identify specific features of the Grover Search Algorithm's second operator (picture in post, further on "$Us$"), which mirrors the system relative ...
Andre R.'s user avatar
5 votes
0 answers
148 views

Open problems in quantum algorithms

I am new to the field of quantum algorithms. It is well known that quantum algorithms offer a speedup over classical algorithms in some problems. Regarding the problems in which quantum algorithms ...
Omar Ali's user avatar
  • 151
5 votes
0 answers
58 views

Can anybody explain or suggest a good reference on how to make a modular exponentiation circuit for N=15 with any coprime base?

I have read many papers related to it but in every paper, they just show the circuit of order finding algorithm for N=15, but did not explain what is the procedure to make it. It will be great if ...
Sshingh's user avatar
  • 61
5 votes
0 answers
151 views

How can I express controlled unitary operation in QPE of this implementation of HHL?

I have found this implementation of HHL, and I don't understand why the controlled unitary operation is expressed in the form of $\exp(i t_0 A/2)$ and $\exp(i t_0 A/4)$. The rotation of $\pi$ and $\...
Macalcubo's user avatar
  • 133
5 votes
0 answers
127 views

Why is there no $N$ in the time complexity of the QLSP algorithm by Childs et al.?

The paper Quantum linear systems algorithms: a primer by Dervovic et al has this table on page 3: I'm not sure why there's no $N$ in the time complexity of the algorithm by Childs et al. i.e. $\...
Sanchayan Dutta's user avatar
4 votes
0 answers
48 views

Quantum volume calculation: what is the significance of the value 2/3 for probability to observe a heavy output in the definition of achievable depth?

I am looking into the algorithm to calculate the quantum volume of a given quantum computer. The one thing that is unclear to me is how the achievable depth is defined. In Andrew W. Cross, Lev S. ...
QVolume's user avatar
  • 41
4 votes
0 answers
80 views

What is the total number of qubits required for the Harrow-Hassidim-Lloyd algorithm?

I am fairly new to Quantum Computing and I know a bit of Linear Algebra. I am currently working on the HHL algorithm, I'm having confusion as to how many qubits are actually required in the circuit ...
Subhradeep Sarkar's user avatar
4 votes
0 answers
98 views

If you had a 100 qubit fully fault-tolerant quantum computer, what would you do?

As quantum computers improve, eventually we may have error-corrected devices that have very low error rate. However, many applications (Shor's algorithm, quantum chemistry) appear to require thousands ...
shixian105's user avatar
4 votes
0 answers
168 views

How does edge-coloring help for quantum walks?

Reviewing Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman's famous 2002 welded-trees problem, a quantum Theseus can find his way out of a labyrinth having an exponential number of rooms (vertices),...
Mark Spinelli's user avatar
4 votes
0 answers
63 views

When is a quantum algorithm considered to have a significantly superior performance over another quantum algorithm?

Suppose we have two heuristic quantum algorithms $A$ and $B$ that attempt to solve a certain class of optimization problems. Let's suppose that the benchmarking metric is Time To Solution (TTS), which ...
MonteNero's user avatar
  • 2,684
4 votes
0 answers
45 views

How could one use Grover's algorithm to find pairs of elements?

Imagine we have a set of distinct natural numbers which we divide into two unsorted lists $A$ and $B$. Then, there is a third list $E$ containing pairs of (pairwise) distinct natural numbers. We would ...
VVAV's user avatar
  • 41
4 votes
0 answers
127 views

Quantum Algorithm to Determine if two vectors are orthogonal

I have seen some sources use a quantum algorithm to estimate inner products between two states. The algorithm used from this answer is shown here: But this algorithm has limitations; if the inner ...
Loic Stoic's user avatar
4 votes
0 answers
79 views

How is this Variational Quantum Singular Value Decomposition paper efficient in any way?

Link to paper here. This algorithm seems neat but the unitary decomposition of the matrix M generally takes an exponential number of Pauli basis elements in the number of qubits $N$, therefore an ...
JoJo's user avatar
  • 99
4 votes
0 answers
98 views

What are the main approaches allowing to efficiently simulate quantum circuits, and which hypotheses those circuits have to fulfill

In general, it is very computationally intensive to simulate the evolution of a quantum system. However, in some particular cases, an efficient classical simulation of a quantum algorithm is possible. ...
Marco Fellous-Asiani's user avatar
4 votes
0 answers
159 views

Solving Wordle using quantum computing

I have read everything available on how to solve Wordle using many different strategies ( classical approaches ) However, I wonder if Wordle can be approach using Quantum computing to solve the ...
n22's user avatar
  • 183
4 votes
0 answers
98 views

What is the most efficient method to update the binary encoded values inside a quantum state?

We're implementing a QML algorithm in which we have to update the value stored inside a quantum state which is strictly unknown to us, by multiplying it with a real number classically stored with us. ...
Rohan Bhatia's user avatar
4 votes
0 answers
95 views

Partial measurement can be replaced with constant overhead

While reading the chapter on Quantum Computation (starting on page 401) of the draft version of the Arora & Barak book I came across exercise §4 on page 431 that reads as: Suppose that $f$ is ...
3nondatur's user avatar
  • 173
4 votes
0 answers
118 views

How to optimise QAOA

I have a similarly naive question about the classical part of the optimisation in the Quantum Approximate Optimization Algorithm. Specifically, the cost function is given prescribed as \begin{align} ...
user39726's user avatar
4 votes
0 answers
720 views

What exactly is the "quantum singular value decomposition"?

I know what is singular value decomposition, meaning given a matrix and write it as multiplication three different matrices, and middle matrix being diagonal and entries are singular values. So, what ...
Jaimin's user avatar
  • 188
4 votes
0 answers
123 views

Does noise model in qiskit impact the optimized parameters for QAOA?

I have read this paper about the effects of quantum noise on QAOA. In the conclusion, it says: QAOA is a noise-tolerant algorithm, quantum noise does not change the QAOA quantum circuit parameter ...
peachnuts's user avatar
  • 1,393
4 votes
0 answers
54 views

Are there direct usefull applications of the quantum Fourier transform not requiring heavy other subroutine

I know that the quantum Fourier transform has many applications such as order finding (which is used in Shor algorithm), phase estimation, etc. However those algorithms require extra subroutines which ...
Marco Fellous-Asiani's user avatar
4 votes
0 answers
106 views

What is the algorithm for the optimal decoder in a quantum erasure channel?

I'm reading this paper : Holographic Quantum Error Correcting Codes and on page 3 they describe an optimal decoder for erasure channel. The description is for CSS codes but they claim that "it is ...
unknown's user avatar
  • 2,217
4 votes
0 answers
69 views

Feynman method and polynomial time algorithm for XQUATH

Consider the Feynman algorithm for simulating quantum circuits, as given here. Consider the XQUATH conjecture for random quantum circuits from here, given by (XQUATH, or Linear Cross-Entropy Quantum ...
BlackHat18's user avatar
  • 1,363
4 votes
0 answers
127 views

An algorithm to perform Gram-Schmidt orthogonalization of linearly independent state vectors

In the first paragraph of the 2nd section of this article, it is stated that given a set of linearly independent $n$-qubit state vectors, Alice can perform the Gram-Schmidt procedure to obtain ...
IamKnull's user avatar
  • 483
4 votes
0 answers
71 views

Calculating symplectic dual of a code

Stabilizer codes can be treated as symplectic codes over $\mathbb{F}_2$ (or over $\mathbb{F}_p$ when taking about q-dits). While treating error class, symplectic dual of the code plays a crucial part (...
Root's user avatar
  • 509
4 votes
0 answers
81 views

Can Grover's algorithm be applied to differential equation solving?

As I understand Grover's algorithm, given the output of a black-box function, can be used to find the corresponding input (or set of inputs if the function is not one-to-one). It is therefore ...
thegreatemu's user avatar

1
2 3 4 5