Questions tagged [algorithm]
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.
185
questions with no upvoted or accepted answers
13
votes
0
answers
370
views
Are all quantum algorithms hidden subgroup algorithms?
I am reading the paper "Quantum Hidden Subgroup Algorithms: An Algorithmic Toolkit" by Samuel Lomonaco and Louis Kauffman from the book, "Mathematics of Quantum Computation and Quantum ...
- 307
11
votes
0
answers
193
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 ...
- 459
8
votes
0
answers
150
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 ...
- 321
8
votes
0
answers
381
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 ...
- 9,366
8
votes
0
answers
84
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 ...
- 9,366
8
votes
1
answer
448
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 ...
- 81
8
votes
0
answers
350
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)...
- 52.3k
7
votes
0
answers
58
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-...
- 326
7
votes
0
answers
100
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 (...
- 79
7
votes
0
answers
59
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 ...
- 11k
7
votes
0
answers
82
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 ...
user5438
7
votes
0
answers
248
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 ...
- 323
6
votes
0
answers
163
views
How to translate between continuous variable model and discrete model?
If I understand correctly, the discrete and continuous variable (CV) version of quantum computation are equivalent. However, the continuous aspect of the CV model makes me wonder to what extent can ...
- 2,013
6
votes
1
answer
252
views
Register size in factoring 15 using Shor's algorithm
In Nielsen and Chuang's book: Quantum computation and quantum information (2016), there is an example in Box 5.4 which shows how to factor $15$ using Shor's algorithm. I am confused about a ...
- 61
6
votes
0
answers
103
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 ...
- 1,119
6
votes
1
answer
484
views
How can I run a VQE on one of IBMQ's Quantum Computers
I have implemented a VQE based on Qiskit's VQE function and want to run that on an actual quantum computer. My understanding was, that an IBMQ backend can be passed into the function as a Quantum ...
- 61
6
votes
0
answers
85
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 ...
- 1,119
6
votes
0
answers
111
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?
- 794
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?
- 301
6
votes
0
answers
140
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 ...
- 16.9k
5
votes
0
answers
114
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 ...
- 51
5
votes
2
answers
159
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 ...
- 555
5
votes
0
answers
110
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 ...
5
votes
0
answers
230
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/...
- 73
5
votes
0
answers
56
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 ...
- 849
5
votes
0
answers
135
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 ...
- 51
5
votes
0
answers
133
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 ...
- 151
5
votes
0
answers
57
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 ...
- 61
5
votes
0
answers
136
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 $\...
- 133
4
votes
0
answers
88
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),...
- 9,366
4
votes
0
answers
71
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 ...
- 383
4
votes
0
answers
50
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 ...
- 89
4
votes
0
answers
104
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 ...
- 371
4
votes
0
answers
48
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 (...
- 459
4
votes
0
answers
64
views
What is the computational complexity of approximate quantum adders, in terms of big O notation?
I have recently found papers on approximate quantum adders. However, the papers do not seem to mention the computational complexities of their algorithms. What are their complexities, in terms of big ...
- 339
4
votes
0
answers
58
views
In the HHL algorithm, how large should the eigenvalue estimation register be?
In the HHL algorithm, we need to estimate the eigenvalues of a matrix $A$. The result is stored in a register with $l$ qubits. Let $T = 2^l$. $T$ cannot be too small, otherwise the result would have a ...
- 141
4
votes
0
answers
91
views
How one would implement the circuit to create superpositions corresponding to efficiently integrable probability distributions?
See article here: https://arxiv.org/abs/quant-ph/0208112
There are two steps in this procedure that I am curious about. First off, they suppose one can construct a circuit which efficiently performs ...
- 439
4
votes
0
answers
55
views
Variances of the principal components in Ewin Tang's PCA algorithm
In Quantum-inspired classical algorithms for principal component analysis and supervised clustering, the PCA algorithm requires that the variances of the principal vectors differ by at least a ...
- 157
4
votes
0
answers
269
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 ...
- 377
4
votes
0
answers
88
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 ...
- 1,620
4
votes
2
answers
1k
views
In Grover, how to implement oracle and amplification using Qiskit?
I found some examples of implementing the oracle when the marked state is $|000\rangle$.
But how can we know what gate we should use inside of the oracle?
Besides, for the part implementation, the ...
- 1,303
4
votes
0
answers
236
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.
$$
\text{...
4
votes
0
answers
61
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 ...
- 141
4
votes
0
answers
1k
views
Could quantum computing improve chess engines?
Could and how quantum computing improve chess engines? Will it be able to think much faster and better than a classical chess computer?
Will a quantum computing chess engine be drastically better ...
- 41
4
votes
0
answers
90
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 ...
- 5,770
4
votes
0
answers
139
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 ...
user7451
4
votes
0
answers
140
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 ...
- 9,366
4
votes
0
answers
447
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 &...
- 247
4
votes
0
answers
100
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, ...
- 1,601
4
votes
0
answers
110
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. $\...
- 16.9k