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.

43 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
13
votes
0answers
292 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
164 views

Quantum walk with binary tree

I’m trying to grok quantum walks, and would like to create an example that walks a perfect binary tree to find the one and only marked leaf node. Is this possible? If so, suppose the depth of the tree ...
9
votes
0answers
138 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
260 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, ...
6
votes
0answers
113 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
51 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
71 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
214 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
119 views

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

Note: Cross-posted on Theoretical Computer Science SE. This question is inspired by thinking about quantum computing power with respect to games, such as chess/checkers/other toy games. Games fit ...
5
votes
0answers
133 views

Circuit construction for Hamiltonian simulation

I would like to know how to design a quantum circuit that given a Hermitian matrix $\hat{H}$ and time $t$, maps $|\psi\rangle$ to $e^{i\hat{H}t} |\psi\rangle$. Thank you for your answer.
5
votes
0answers
102 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
51 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
103 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
160 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
33 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
40 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
98 views

Does HHL implementation require a priori eigendecomposition?

I am interested in HHL algorithm and despite all the problems related to current technologies, I am trying to understand how it has to be implemented. I have seen from these two available circuits (...
4
votes
0answers
172 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
56 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
59 views

Quantum comparator with one fixed input

I currently need to implement efficiently a quantum comparator, with one of the values that is known at generation-time. In other words, I am searching for a quantum routine ...
3
votes
0answers
79 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
53 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
56 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
82 views

What can be some bachelor thesis ideas in quantum random walks?

Note: Cross-posted on Theoretical Computer Science Stack Exchange. I am an undergraduate, reading about quantum information and quantum technology. For about some time, I have been interested in the ...
3
votes
0answers
58 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
0answers
66 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 ...
3
votes
0answers
79 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
132 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 ...
3
votes
0answers
64 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
113 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
21 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 ...
2
votes
0answers
79 views

Grover diffusion operator different gates

I have two gates here for the Grover diffusion operator. The first gate is completely understandable for me, so I implemented it myself after submitting some papers that I read. This is the first ...
2
votes
0answers
39 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 ...
2
votes
0answers
160 views

Possible results from Shor's algorithm in practice

After reading through Shor's algorithm, I have a few questions about the probability of factoring semiprime number out. Here is some background of the question. To factor a semiprime number $N$ such ...
2
votes
0answers
58 views

Optimal sampling strategy for VQE

In VQE we wish to minimize some cost function $F(\vec{x})$ that is dependent on a quantum state $\left| \psi_\vec{x} \right>$ which is prepared by a unitary $U(\vec{x})$ depending on some (...
2
votes
0answers
55 views

Does Brassard's algorithm for calculating the mean make implicit assumptions on distribution?

In An optimal quantum algorithm to approximate the mean and its application for approximating the median of a set of points over an arbitrary distance Brassard presents a quantum algorithm for finding ...
2
votes
0answers
25 views

Speedup Prange ISD using Grover

In his 2009 paper, Grover vs McElicee, Bernstein proposed to use the Grover's algorithm to obtain a quadratic speedup on the Prange ISD. However, it is not quite clear to me in which part of the ...
2
votes
0answers
81 views

Would this quantum algorithm implementation work?

I am trying to implement the order finding algorithm on Cirq finding the minimal positive $r$ for coprime $x$ and $N$ satisfying the equation $x^r \ = \ 1$(mod$ \ N$). In my case, I have set $x \ = \ ...
2
votes
0answers
58 views

Pointer to related research (paper)

Recently, I was reading a paper (arXiv:1804.03719 [cs.ET]), which had the following quote (the most relevant part has been bolded), Quantum algorithms are often grouped into number-theory-based, ...
1
vote
0answers
14 views

Ansatz Techniques to Multi-Body Physics Problems

I have been reading this paper: https://arxiv.org/abs/1906.01563v1. I am wondering: is it possible to use the idea behind quantum circuits to build classical Hamiltonians represented in the same way?...
1
vote
0answers
58 views

Extrapolation of CRISPR

Can quantum computing do a simple simulated extrapolation of CRISPR (clustered regularly interspaced short palindromic repeats) projects using a limited number of variables? I mean something like ...
0
votes
0answers
266 views

FPGA qubit simulation

This question is regarding the simulation of qubits, using FPGAs. My question is: how does using FPGAs to simulate qubits help us understand or give us an insight into how quantum computers could be ...
-2
votes
0answers
33 views