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,099
questions
1
vote
1
answer
105
views
Problem with eigenvalue evaluation algorithm application on matrix $U$
Once I get to the end of the algorithm, I can't understand how to calculate the eigenvalue using formulas. Bear in mind that it is an exercise to be carried out with pen and paper.
the matrix of $U$ ...
- 13
2
votes
0
answers
44
views
Are there quantum algorithms to estimate the partial transpose?
The entanglement negativity and the positive partial-transpose criteria play important roles in quantifying the amount of entanglement for mixed states. Yet, because these measures generally involve ...
- 735
3
votes
1
answer
91
views
How much complexity is required to implement $\text{C$_\Pi$NOT}$ gate?
The projector-controlled not gate $\text{C$_\Pi$NOT}$ is defined as
$$\text{C$_\Pi$NOT} \, \colon= \Pi \otimes X + (\mathbb{I}-\Pi)\otimes\mathbb{I}\,, \tag{1}$$ in András Gilyén et. al. (2018)[arXiv:...
- 63
1
vote
0
answers
10
views
Outputing classification probability from the Qiskit VQC
I am new to Qiskit. For the last few days, I have been trying to train my first VQC to do some classification task. Now the VQC is successfully running but it could only output a label whenever I ask ...
- 11
1
vote
0
answers
61
views
Can Amplitude Amplification amplify an unknown state?
If you have for example the basis states $|000\rangle$ and $|xxx\rangle$. The value of the second basis state is unknown, but the amplitude of both states is given. Also the amplitude of the second ...
- 35
1
vote
1
answer
25
views
Quantum improvement in collision-free ID assignment problem?
Consider the following: you are a network device that is in charge of assigning unique identifiers (consisting of $b$ bits) to new devices as they join the network. However, you do not have very much ...
2
votes
0
answers
21
views
Can adiabatic quantum computing be used to find local minimum instead of ground states?
We know that with unfriendly energy gap circumstances, adiabatic quantum computing takes exponential time to find a ground state of some hamiltonian. But if some local minimum state is all we look for,...
- 457
1
vote
1
answer
100
views
How do I apply Amplitude Amplification for following state?
I have a multi qubit state that consists of two basis states and looks like the following for different number of qubits:
2 qubits: $|00⟩+|xx⟩$
3 qubits: $|000⟩+|xxx⟩$
4 qubits: $|0000⟩+|xxxx⟩$
...
(...
- 35
1
vote
1
answer
37
views
How is a linear combination of pauli operators applied to a quantum circuit in qiskit?
Consider a quantum circuit of 2 qubit:
quantumcircuit = QuantumCircuit(2)
If one wishes to apply a Pauli-X operator to the first qubit, one writes:
...
- 510
2
votes
1
answer
77
views
How to measure in $\sigma_x$ basis in Qiskit? [duplicate]
As we know, Qiskit can give us the results of our measurements in computational or, better to say, $\sigma_z$ basis. However, I am courageous about measuring the qubit in, for instance, $\sigma_x$ ...
- 77
4
votes
0
answers
40
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. ...
- 41
5
votes
2
answers
143
views
Why is it hard to prove complexity bounds for variational algorithms?
I'm not very familiar with variational algorithms, but I've heard people say that they're "heuristic" and it's difficult to measure their performance via complexity analysis. Why is this the ...
- 145
1
vote
0
answers
21
views
ZNE for mitigating errors in probability distribution results
Can ZNE be applied to mitigate errors for getting the probability distribution in the computational basis rather than mitigating errors for calculation of expectation values?
- 101
3
votes
0
answers
27
views
Retrieving job result attributes in Qiskit
I am trying to optimize a Hamiltonian using QAOA in IBM Qiskit.
I used the following 'minimize' function to get my result. (I am not including the whole code because it will get unnecessarily long).
<...
- 31
2
votes
0
answers
34
views
What's a quantum algorithm in the black box model to find $j_1,j_2$ such that $f(x_1,...,x_n)=x_{j1}\oplus x_{j2}$?
Consider the set of all functions $f : \{0, 1\}^n → \{0, 1\}$ that are of the form $f(x_1, x_2, . . . , x_n) = x_{j1}\oplus x_{j2}$
for some distinct $j_1, j_2 \in \{1, 2, . . . , n\}$. Suppose that ...
- 51
3
votes
0
answers
26
views
How can one use QAOA to obtain parameters that approximate the first excited state of the target Hamiltonian?
One can use QAOA to find the ground state and its energy by minimizing the expectation value of a target Hamiltonian (say, $H_T$) with respect to the QAOA ansatz and obtaining optimal parameters ...
1
vote
0
answers
24
views
how to measure $Tr[M\rho_1N\rho_2]$ on NISQ devices?
To evaluate $Tr[M\rho]$ with $M$ and $\rho$ a tensor product of Pauli operators and a density matrix, respectively, we just need to prepare the state $\rho$ and then measure it in the $M$-eigenbasis.
...
- 89
1
vote
0
answers
17
views
How to implement the graph adjacency array model?
The paper "Quantum query complexity of some graph problems" by Durr et al. introduces the adjacency array model as a way of storing a graph on a quantum computer. For a vertex $v_i$ of ...
- 11
1
vote
0
answers
40
views
Quantum Lookup Table circuit
I am trying to use the paper "A Realizable GAS-based Quantum Algorithm for Traveling Salesman Problem (2022)". However, it never explains how the index converter works, beyond it being a ...
2
votes
1
answer
69
views
Does the quantum state fidelity satisfy $F(\rho ,\sigma) \le F(\mathcal{A}(\rho), \mathcal{A}(\sigma))$ if ${\cal A}$ is a process involving ancillae?
It is a well known fact that the fidelity is preserved by unitary evolution, i.e.
$$
F(\rho ,\sigma) = F(U\rho U^\dagger, U\sigma U^\dagger),
$$
for any unitary operator $U$.
However in most quantum ...
- 319
3
votes
0
answers
31
views
Intuition for failure of strong Fourier sampling for the symmetric group
I am trying to read and understand the following two papers:
The Symmetric Group Defies Strong Fourier Sampling: Part I
The Symmetric Group Defies Strong Fourier Sampling: Part II
I have a pretty good ...
- 279
0
votes
0
answers
56
views
Is it possible to simulate a quantum algorithm on a classical computer? [duplicate]
I am designing a quantum algorithm that I would like to simulate and test, but I need to be able to simulate it on a classical computer.
- 19
1
vote
2
answers
93
views
A Decision Algorithm That Maybe Related to Quantum Search
As is well known Grover's algorithm can invert a function on a domain of 2^n possible values in other words it can find an x such that f(x)=1 if such an x exists for the oracle f(x). Suppose we are ...
- 57
2
votes
2
answers
61
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 ...
- 510
2
votes
2
answers
111
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
3
votes
2
answers
322
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 ...
- 43
1
vote
0
answers
23
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
28
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
92
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$ ...
- 279
3
votes
0
answers
76
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
71
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
93
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
30
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. ...
4
votes
1
answer
137
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>...
- 106
1
vote
1
answer
66
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
0
answers
30
views
Pennylane variational classifier demo - need for padding
In the variational classifier demo from Pennylane, the data loading is performed with
...
3
votes
0
answers
45
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
47
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
79
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
46
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
213
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 ...
- 145
2
votes
2
answers
59
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
51
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
20
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
55
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♦
- 23.3k
1
vote
1
answer
48
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♦
- 23.3k
1
vote
1
answer
73
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♦
- 23.3k
3
votes
2
answers
108
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
21
views