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.
1,172
questions
2
votes
2
answers
68
views
gate actions in classical (not in the physics sense) superdense coding narrative
I am currently reading through superdense coding and the setup is as follows:
Both Alice and Bob shares a fixed entangled state $|\psi\rangle = \frac{1}{\sqrt{2}}[|00\rangle + |11\rangle]$ with the ...
- 520
2
votes
2
answers
117
views
Is there a quantum algorithm for this?
While a well-established quantum algorithm exists for finding an estimate of the phase of the eigenvalue of a unitary matrix, the following question has a bit of a different requirement. Suppose we ...
- 57
5
votes
2
answers
750
views
What is a Hadamard test?
What is a Hadamard test? I have seen this term at many places in video lectures and on various weblinks.
A detailed answer on this would be a great help. This is what Wikipedia says, but I really ...
- 63
1
vote
0
answers
36
views
Comparing BQM and CQM solving for a tree-path problem
I'm currently working on a project for my thesis regarding BQM and CQM optimisation for a path problem.
Without going too much on the details, here's some info:
the structure is a tree, where all the ...
1
vote
0
answers
69
views
An unexpected result of the Implementation of a finding minimum values algorithm using a qRAM
Motivated by the article Quantum algorithm for finding minimum values in a Quantum Random Access Memory, I'm training to implement a simplified version of the proposed algorithm. But the output isn't ...
- 11
3
votes
1
answer
109
views
What is the initial state in the second register in Shor's algorithm?
Following up on this question, can someone help me clear up the notation we're using for states in Shor's algorithm? It's very unclear what the sentence "where the second register is $|1\rangle$ ...
- 299
3
votes
0
answers
85
views
Complexity of the quantum circuits that are needed to implement communication protocol?
Consider the following simultaneous communication problem. Alice and Bob do not share any
entanglement or any common randomness, and cannot communicate directly with each other. As
inputs, x is given ...
- 31
2
votes
1
answer
108
views
Quantum computation of classical Fisher information
Consider a pure $n$-qubit quantum state $|\psi_\theta\rangle$ prepared by some parametrized quantum circuit. There exist well-known algorithms to efficiently estimate the quantum Fisher information ...
- 23
2
votes
0
answers
109
views
Can D-Wave presently solve real-world problems that conventional computers cannot solve?
There are number of threads on this site about the ability of QCs solving real-world problems (see for example What are the practical applications of quantum computing in engineering by the year 2030?,...
- 85
2
votes
0
answers
44
views
How to calculate number of qubits required for Grover Algorithm while constructing it's oracle and diffuser for any Specific Algorithm or Hash?
I am reading a paper titled, " (Towards Post-Quantum Secure Symmetric Cryptography:
A Mathematical Perspective)". Here, I am able to understand the gate counts and T-depth calculations. ...
5
votes
1
answer
164
views
What is the hidden subgroup in Deutsch-Jozsa?
It is noted by several sources (e.g. this paper) that the problem solved by the Deutsch-Jozsa (DJ) algorithm is an instance of the Hidden Subgroup Problem (HSP). However, I fail to see this for $n>...
- 116
1
vote
1
answer
76
views
How can I derive the very basic formulas used in Grover's algorithm?
I have been studying the Grover's algorithm for quite some time. I have used David McMohan (Quantum Computing Explained), M. Suhail Zubairy (Quantum Mechanics For Beginners) and some research papers. ...
1
vote
1
answer
67
views
Pennylane variational classifier demo - need for padding
In the variational classifier demo from Pennylane, the data loading is performed with
...
5
votes
0
answers
78
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 ...
0
votes
0
answers
49
views
How to best implement this algorithm?
I am trying to design an algorithm to find a solution to a certain problem. I have N qubits which encode the problem (let's call them the problem qubits) and one check_qubit (which is flipped to |1>...
- 195
0
votes
0
answers
31
views
The possibility of a Quantum image classifier
I want to create an exhaustive database of all possible contour images(B&W) with their image tags, for a given resolution.
By classifying every single image possible for the resolution, I want to ...
- 111
4
votes
0
answers
92
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 ...
- 173
3
votes
1
answer
58
views
Simulating Sparse Hamiltonians: help understanding query complexity bounds
tl;dr: How can I show that $e^k/k^k$ is less than $\epsilon^2/2$ when $k=\Omega\left(\frac{\log(1/\epsilon)}{\log \log(1/\epsilon)}\right)$, where $k,\epsilon\in \mathbb{R}$ and > 0?
Context:
Berry ...
- 33
4
votes
2
answers
256
views
When is it justified to have an oracle in a quantum algorithm?
I've always been confused as to when a quantum algorithm is allowed to have an oracle and what kind of a function the oracle can have. For instance, I know in Hamiltonian simulation algorithms, you ...
- 155
2
votes
2
answers
93
views
Visual the qubit state after amplitude encoding
I trying to visualize qubits state after amplitude encoding.
I have the following code which takes the 8 feature [1/2, 1/2, 1/2, 1/2,1/2, 1/2,1/2,1/2] and encodes into 3 qubits.
I now get the output [...
1
vote
0
answers
54
views
The possibility of an image classifier using quantum computer architecture?
Consider an exhaustive database of all contour images that can ever be created on a 16x16 grid. Out of the $2^{256}$ unique possibilities, could a quantum computer classify all the resulting images ...
- 111
0
votes
0
answers
21
views
Help to make the equations of state of qubits?
.., and find their cofacents, after H(q1) ->CNOT(q1,q2) -> H(q2)
On the website https://algassert.com/
The preparation is like this. I understand so far
The preparation is like this. I ...
3
votes
0
answers
61
views
What's an example of a superposition $\sum_i \sqrt{p_i}|i\rangle$ that cannot be prepared efficiently?
As also discussed in (How does the induction step in the Grover-Rudolph scheme to prepare superpositions from probabilities work? and How does the uncomputation step work in the Grover-Rudolph scheme ...
glS♦
- 24.9k
1
vote
1
answer
99
views
How does the uncomputation step work in the Grover-Rudolph scheme to prepare $\sum_i\sqrt{p_i}|i\rangle$?
In https://arxiv.org/abs/quant-ph/0208112, the authors discuss a scheme to, given a discrete probability distribution $\mathbf p\equiv (p_i)_i$, under some assumptions on $\mathbf p$, prepare the ...
glS♦
- 24.9k
1
vote
1
answer
153
views
How does the induction step in the Grover-Rudolph scheme to prepare superpositions from probabilities work?
In https://arxiv.org/abs/quant-ph/0208112, the authors discuss a scheme to, given a discrete probability distribution $\mathbf p\equiv (p_i)_i$, under some assumptions on $\mathbf p$, prepare the ...
glS♦
- 24.9k
3
votes
2
answers
151
views
In Deutsch–Jozsa algorithm, why one can safely ignore the last qubit of oracle output?
Wikipedia article about Deutsch-Jozsa algorithm says, under the section Algorithm, that:
At this point the last qubit, $$\frac{|0\rangle - |1\rangle}{\sqrt{2}}$$ may be ignored.
Does it mean that, ...
- 133
1
vote
1
answer
40
views
0
votes
0
answers
21
views
What are the quantum algorithms available for Monte Carlo sampling?
What are the quantum algorithms available for performing Monte Carlo sampling. Is there any implementation of these algorithms. Any kind of resources would be helpful
- 31
2
votes
3
answers
124
views
Seeking Programming Projects and Tools for Quantum Gate Decomposition Implementations
The Solovay-Kitaev theorem shows that "this approximation can be made surprisingly efficient, thereby justifying that quantum computers need only implement a finite number of gates to gain the ...
- 141
2
votes
0
answers
74
views
Is the QFT optimal in the quantum phase estimation algorithm?
We can concisely summarise the quantum phase estimation (QPE) algorithm as follows:
Generate the state $\sum_{k=0}^{2^n-1} \lambda^k |k\rangle$ efficiently using a series of controlled-unitary ...
glS♦
- 24.9k
2
votes
1
answer
150
views
Does subtraction circuit have a class like full or half Carry adder circuit in qiskit? one subtraction circuit code-example in qiskit?
I need a subtraction circuit to calculate Laplacian in edge processing, but I didn't find any class in qiskit.Do I have to write the code myself?
- 21
1
vote
0
answers
572
views
Two-way quantum computers (like in Ising model) - are they possible? Could solve general NP problems? [closed]
Standard one-way quantum computers (1WQC) allow for e.g. Shor, Grover algorithms, however, general NP problems seem too difficult for them(?) - bringing an open question if they could be somehow ...
- 53
0
votes
0
answers
35
views
Exponential modulation on qiskit, Shor algorithm [duplicate]
I´m trying to code the shor algorithm for any N and any a but i always find examples of code for the N=15. My first question is how is this funtion( provided by qiskit ) does the exponential ...
6
votes
0
answers
71
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 ...
- 155
3
votes
1
answer
183
views
Determining the number of qubits to represent the eigenvalues in HHL algorithm?
I am trying to understand how well the HHL algorithm would scale. Therefore my first inquiry is how the number of qubits scale with the size of the problem ie the size of the Matrix A in the linear ...
3
votes
1
answer
157
views
What quantum algorithms can be used to solve for eigenstates and eigenvalues of a hermitian matrix?
I am working with a tight binding model. I am looking for a way I can efficiently find the eigenvalues and eigenvectors of the Hamiltonian using a quantum algorithm. Can someone suggest some good ...
- 169
0
votes
0
answers
37
views
Why are the other qubits affected by a phase flip in Shor's 9-qubit code?
We have the following "concatenated" initial state in the 9-qubit Shor code:
$\alpha{(|000\rangle+|111\rangle)(|000\rangle+|111\rangle)(|000\rangle+|111\rangle)}/{2\sqrt{2}}+\beta{(|000\...
- 147
12
votes
1
answer
692
views
How are quantum algorithms devised?
This is a soft question, but I find it to be a very pertinent one...
Algorithms for Grover's search and Simon's problems seem to come completely out of the blue, and I find it very hard to understand ...
- 147
2
votes
3
answers
335
views
How do we measure the probability of outcomes in a quantum computer if qubits collapse when measured?
I understand the idea behind Quantum Computing being that we superpose all possible states of a system of qubits and amplify the probabilities of whatever it is that we want depending on the circuit ...
- 89
1
vote
1
answer
109
views
General Grover's search showing wrong results on a particular instance
I am trying to implement a general Grover's search for n qubits searching for m marked elements. I happened to observe that for ...
- 43
2
votes
1
answer
73
views
Is there something like error-suppression codes?
My question is a bit on the soft side, and basically asks if there is something between error mitigation and full error correction?
On the one hand, as far as I understand, trying to increase the ...
- 1,605
1
vote
0
answers
82
views
Heuristics on Quantum computers
I found the article :
Strengths and Weaknesses of Quantum Computing, 1997
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh Vazirani
As far as I understand, this one states that quantum ...
- 131
1
vote
0
answers
122
views
Why can Shor code fix arbitrary errors?
This is taken from Page 434 of Nielsen and Chuang:
To simplify the analysis, suppose noise of an arbitrary type is occurring on the first
qubit only; we’ll come back to what happens when noise is ...
- 147
0
votes
1
answer
55
views
Why is "this" particular decomposition/regouping of states observed?
This question is motivated from this as well as the regrouping of terms in Shor code.
The setup is not important, but it is being provided for context.
$|\psi\rangle=\alpha|0\rangle+\beta|1\rangle$
$|...
- 147
0
votes
2
answers
167
views
Is there a quantum algorithm for the closest vector problem on a 2-dimensional lattice?
Is there a standard quantum algorithm (adiabatic or density matrix based) that can output the answer to a 2-dimensional closest vector problem:
ie. find the closest lattice point (the blue one) that ...
- 491
1
vote
1
answer
100
views
How to read the result of this HHL algorithm circuit output?
I have computed the final states of a 1-qubit HHL circuit using initial conditions
$$ A|x\rangle = |b\rangle$$
$$\begin{bmatrix} 8 & 6+i \\ 6-i & -1\end{bmatrix} |x\rangle = \begin{bmatrix} \...
- 491
1
vote
1
answer
55
views
Verification for calculation on Shor's code
Here I have tried to determine the end result for the qubit states, when we apply an arbitrary gate on the first qubit in the 9 qubit code.
I have followed this diagram:
U's operation on a qubit can ...
- 147
0
votes
0
answers
49
views
Random variable as tensor product of its components
Consider a finite random variable $X: \Omega \rightarrow \mathbb{R}^d$ on a probability space $(\Omega, 2^{\Omega}, P)$. Let $H_{\Omega}$ and $H_E$ be two Hilbert spaces with basis states $ \{| \omega ...
- 41
2
votes
0
answers
59
views
GPU Support for Qiskit's SPSA Optimization Algorithm
I am using Qiskit's SPSA optimization algorithm to find the ground state energy of various lattices (fermi-Hubbard model) by running different circuits through it and having the algorithm modify the ...
-1
votes
1
answer
136
views
4-cities traveling salesman quantum algorithm (QUBO)
A quantum version of the traveling salesman algorithm is discussed here:
There is a reference to QUBO, Ising, and some matrix constructions,
and the output in the end:
Is anyone able to run through ...
- 491