# 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
Filter by
Sorted by
Tagged with
1 vote
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$ ...
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 ...
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_\PiNOT} \, \colon= \Pi \otimes X + (\mathbb{I}-\Pi)\otimes\mathbb{I}\,, \tag{1}$$ in András Gilyén et. al. (2018)[arXiv:...
1 vote
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 ...
1 vote
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 ...
1 vote
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 ...
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,...
1 vote
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⟩$ ... (...
1 vote
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: ...
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$ ...
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. ...
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 ...
1 vote
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?
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). <...
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 ...
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
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. ...
1 vote
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 ...
1 vote
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 ...
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 ...
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 ...
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.
1 vote
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 ...
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 ...
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 ...
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 ...
1 vote
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
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 ...
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$ ...
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 ...
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 ...
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?,...
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. ...
137 views

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>... 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>... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ...
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, ...