Questions tagged [algorithm]

For questions on quantum algorithms. That is, algorithms which in theory can be executed by quantum computers, usually the computers providing 'universal' quantum computation.

92 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
17
votes
0answers
626 views

Quantum machine learning after Ewin Tang

Recently, a series of research papers have been released (this, this and this, also this) that provide classical algorithms with the same runtime as quantum machine learning algorithms for the same ...
11
votes
0answers
608 views

Is there a list of accessible open problems in quantum computing from a theoretical computer science perspective?

(Classical) theoretical computer science (TCS) has a number of outstanding open problems that can easily be instantiated in a manner that is accessible to a wider general public. For example, ...
9
votes
0answers
179 views

Quantum Walk: Why the need of adding “tail” nodes to the root?

As stated in the question, I have found in several papers (e.g. 1, 2) that in order to perform a quantum walk on a given tree it is necessary to add some nodes to the root $r$, say $r^{'}$ and $r^{"}$....
8
votes
0answers
142 views

What are examples of non-oracular versions of famous oracular problems?

Most quantum algorithms proposed, including Deutsch-Jozsa, Simon's, Bernstein-Vazirani etc, involve querying an oracle. If I understand correctly, the speedups depend on the oracle being efficiently ...
7
votes
0answers
70 views

Status of hidden shift and hidden subgroup problems

We know that solving a hidden subgroup problem over a non-commutative group is a long standing problem in quantum computing even for groups like $D_{2n}$ (alternatively can be written as $\mathbb{Z}_n ...
7
votes
0answers
171 views

Does the GLOA have any advantage over the Solovay-Kitaev algorithm?

The Solvay Kitaev algorithm was discovered long before the Group Leaders Optimization algorithm and it has some nice theoretical properties. As far as I understand, both have exactly the same goals: ...
6
votes
0answers
54 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 ...
6
votes
0answers
110 views

Calculating power of a quantum computer — RSA

As discussed in this question, the expected security of 1024-bit RSA is 80-bits: NIST SP 800-57 §5.6.1 p.62–64 specifies a correspondence between RSA modulus size $n$ and expected security strength ...
6
votes
0answers
254 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 ...
6
votes
0answers
259 views

What is the complexity of the quantum phase estimation in Grover's algorithm?

Suppose we are using GA (Grover's algorithm) such that we are given it has 2 or more solutions. The search space is of size $N$. We all know Grover's algorithm has, at worst, a time complexity ...
6
votes
0answers
63 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 ...
6
votes
0answers
105 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 ...
6
votes
1answer
281 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)...
5
votes
0answers
31 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 ...
5
votes
0answers
64 views

Decomposing Hamiltonian into qubit model representation

One of the main application of VQE is its application to find the approximation to the ground state energy (smallest eigenvalue) for a particular molecule through an iterative method. To be able to ...
5
votes
0answers
38 views

Oracle for welded tree walk

There is a famous paper by Childs, et al, in which it is shown that a quantum algorithm can find the name of the exit node for a certain graph in a way that is exponentially faster than any classical ...
5
votes
0answers
130 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?
5
votes
0answers
57 views

Correspondence between the Topological model and Quantum Circuit model

For example, given the $R$ & $F$ gates and Toric codes for a given problem, how to convert this code into the conventional circuit model and vice versa. From the literature developed, it seems ...
5
votes
0answers
117 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 ...
5
votes
0answers
179 views

Consequences of SAT ∈ BQP

"Quantum magic won't be enough" (Bennett et al. 1997) If you throw away the problem structure, and just consider the space of $2^n$ possible solutions, then even a quantum computer needs about $\...
4
votes
0answers
36 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 ...
4
votes
0answers
32 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 (...
4
votes
0answers
50 views

The relationship between problem structure and exponential speedups under the query model

What problem structure(s) are required to admit an exponential speedup in the universal quantum model of computation under the query model? Intuitively, it would seem that much of the benefit of the ...
4
votes
0answers
141 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/...
4
votes
0answers
28 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 ...
4
votes
0answers
73 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 ...
4
votes
0answers
41 views

Are there any quantum algorithms to compute the norm of a vector, better than the classical version (O(d), where d is dimension)

I am researching how to speedup optimization problems using quantum algorithms. Many such algoritms use the Euclidean norm of a vector. Hence, I tried to find a quantum algorithm that speedups the ...
4
votes
0answers
46 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 ...
4
votes
0answers
52 views

How to determine the minimum number of experiments needed to compute m-many k-local Pauli expectations?

Say I have an algorithm over N qubits and I want to find the expectation value of an operator $O$ composed of a sum of mterms, each of which is the tensor product of some number of single-qubit Pauli ...
4
votes
0answers
186 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 ...
4
votes
0answers
64 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. $\...
3
votes
0answers
68 views

Question Regarding Quantum Period-Finding Fourier Transform Approximation

I am following the 5.4.1 Period-Finding Algorithm in Nielsen and Chuang as shown below: My confusion lies with the second expression of point 3 in the procedure. Why is the second expression an ...
3
votes
0answers
135 views

Using quantum computers to calculate definite integrals?

Question How would a quantum computer calculate a definite integral (without resorting to approximations) of a function? Motivation According to a post of mine (in the context of classical field ...
3
votes
0answers
56 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 ...
3
votes
0answers
53 views

Marriott-Watrous style amplification with a quantum input

$\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 ...
3
votes
0answers
73 views

General mixed integer linear programming problem with quantum computers

I was wondering if anyone had a sample code for running a general MILP problem. I saw some coding for some very specific problems and I thought they were kind of far away from what we needed. If ...
3
votes
0answers
53 views

QAOA and symmetry effects on the angles

In this paper, QAOA on Maxcut shows symmetries that allow them to restrict their search space intervals. But how do they find such intervals knowing that in the original QAOA angles $\gamma,\beta$ are ...
3
votes
0answers
124 views

Quantum Optimization via Quantum Label Classification in Quantum Circuits

I have been reading Farhi and Neven's paper on quantum neural networks on quantum circuits. I also found an example - albeit not ideal as pointed out by a couple of users - thank you - in here. ...
3
votes
0answers
76 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 $\...
3
votes
0answers
87 views

Is HHL executed in a single run? If yes, how do they carry out controlled rotation without knowing eigenvalues?

Even after reading several papers and almost all HHL related questions and answers here on Quantum Computing Stack Exchange, one thing is yet not clear. In several papers, for illustrating HHL they ...
3
votes
0answers
97 views

What are applications of HHL's “simple example” to determine similar stable states of different quantum processes?

The HHL paper "Quantum algorithm for linear systems of equations" [link] initially describes a "simple example" to illustrate the potential power of their algorithm. They state: Consider a ...
3
votes
1answer
100 views

Quantum addressing scheme

Nielsen explains how a search algorithm can access a classic database. I have a few questions. I hope you can help me a bit :) I work with a few quotes from the book. The principle of operation is a ...
3
votes
0answers
165 views

Genetic algorithm does not converge to exact solution

I'm trying to evolve quantum circuits using genetic algorithms as they did in this paper Decomposition of unitary matrices for finding quantum circuits: Application to molecular Hamiltonians (Daskin &...
3
votes
0answers
102 views

How to apply unitary coupled cluster to a spin problem?

I understand how to apply UCC to a problem formulated in a second-quantized (fermion) form: you start with some state and then create a unitary operator out of single-body (or double-, triple- and so ...
3
votes
0answers
82 views

Deutsch Algorithm on a Quantum Turing Machine

I understood how a Quantum Turing Machine works from this lecture. It would be great if someone could give an example of how this machine could be used to solve a real problem though, for example, ...
3
votes
0answers
120 views

Algorithm to allocate tasks and tools fairly to 2 players

Puzzle I have the following puzzle for which I would like to create a quantum algorithm. There are 2 players that need to complete 3 tasks as fast as possible. There are 3 different types of tasks ( ...
2
votes
0answers
23 views

Quantum walk for quantum simulated annealing in arXiv: 1512.03806

I'm studying quantum walk and quantum simulated annealing. While reading the paper Quantum algorithms for simulated annealing, I feel a little confused about the quantum walk they gave in Sec 2.1 ...
2
votes
0answers
45 views

Hadamard Overlap Test

I am trying to understand a test called Hadamard Overlap Test, which consists of a destructive swap test (section IV of swap test and Hong-Ou-Mandel effect are equivalent) right after a Hadamard test. ...
2
votes
0answers
38 views

Is there any published research on quantum fault tolerant circuits that are designed for a specific task or algorithm?

I have searched for works that focus on designing a fault-tolerant quantum circuit for a specialized application and only found 'Error-corrected quantum annealing with hundreds of qubits' by Pudenz, ...
2
votes
0answers
22 views

How to find a marked item out of $K < N$ marked items when K is unknown?

I'm wondering about time complexities of variants of the searching problem in Grover's Algorithm. I know that using G.A. the time complexity required to find a market item reduces to $O(\sqrt N)$. ...