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.

Filter by
Sorted by
Tagged with
1
vote
0answers
80 views

Definition(s) of $\delta$ in quantum phase estimation

I read the chapter on QPE (quantum phase estimation) in Nielsen and noticed that $\delta$ is defined there as follows: $0 \leq \delta \leq 2^{-t}$, see: 5.2.1 Performance and requirements The above ...
3
votes
1answer
34 views

Soundness of Grover's search application

I find that some algorithms can be sped up using Grover's search, but I have a question about the soundness of new algorithms. Since Grover's search is a probabilistic method, it has a chance to make ...
4
votes
1answer
57 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 ...
1
vote
1answer
47 views

Implementation of quantum phase estimation in Quirk

after reading the chapter of QPE (Quantum phase estimation) in Nielsen, I wanted to try an implementation in Quirk. My idea was to apply the T-gate, from which I know the following relation $T|1\...
2
votes
1answer
52 views

How would you apply quantum computing to break a symmetric key system?

How would you apply quantum computing to break a symmetric key system? Do you attack the plaintext password by bruteforcing? Or the mathematical process of the encryption algorithm?
9
votes
1answer
1k views

Can a quantum computer tell whether a program is Turing complete?

I am very new to quantum computing and would like to know if a quantum computer can decide whether a given program is Turing complete.
1
vote
0answers
66 views

How would Quantum Phase Estimation be solved classically?

I would be interested to know how Quantum Phase Estimation (QPE) would be solved classically. So suppose we have a matrix and a vector description of $U$ and $|\psi\rangle$. I would present here what ...
4
votes
2answers
68 views

How is Quantum Phase Estimation useful for simulating dynamics of a many-body system?

I am quite aware of the Quantum Fourier Transform (QFT) as well as the very closely related topic of Quantum Phase Estimation (QPE). The latter is usually motivated as follows: Given a unitary $U$ and ...
4
votes
2answers
92 views

Are there ''interesting'' examples of circuits where gates can all commute each other?

Are there ''interesting'' examples of circuits where gates can all commute each other? More formally, there may be some group of circuits where gates and, particularly, CNOTs (as the only two-qubit ...
0
votes
0answers
47 views

What exactly is the "quantum singular value decomposition"?

I know what is singular value decomposition, meaning given a matrix and write it as multiplication three different matrices, and middle matrix being diagonal and entries are singular values. So, what ...
1
vote
0answers
27 views

What will be the most useful quantum algorithms in the fault-tolerant quantum computers era?

When we'll have fault tolerant quantum computers with a lot of qubits, what will be the most useful algorithms (studied so far)? I know about Shor, Grover and quantum phase estimation but I'm pretty ...
2
votes
0answers
49 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
vote
0answers
17 views

Does noise model in qiskit impact the optimized parameters for QAOA?

I have read this paper about the effects of quantum noise on QAOA. In the conclusion, it says: QAOA is a noise-tolerant algorithm, quantum noise does not change the QAOA quantum circuit parameter ...
3
votes
1answer
166 views

Quantum algorithm to construct an arbitrary superposition of N integers?

Say for 3 qubits, I want a super position of 0 (000), 2 (010), and 7 (111). Is there a general algorithm for building this superposition? Or for an even super position of N integers? Part of me feels ...
2
votes
0answers
34 views

Is molecule simulation by quantum computing critical for drug discovery?

It is often said that the molecule simulation for drug discovery will be one of the most important applications of Quantum Computing (QC). As we all know that the entire process of new drug discovery ...
1
vote
0answers
35 views

Confusion about the objective function of VQEs and QAOAs

I am a bit puzzled on how the objective function of the VQEs and QAOAs. Of course, the parametrised state is constructed differently in these two algorithms but they do share a common objective to be ...
0
votes
1answer
89 views

Phase estimation algorithm: Bounding of probability in Nielsen and Chuang

I am currently studying the Quantum Phase Estimation (QPE) algorithm as described in Nielsen and Chuang, pages 223-224. We have the following situation there, we have the state: $$\frac{1}{2^t} \sum\...
2
votes
1answer
54 views

Grover search with multiple solution implementation strategy

I am confused about how to implement a strategy for Grover's search with multiple solutions. My goal is to find all $t$ solutions in $N$ elements. I got this question because I found people used query ...
2
votes
1answer
94 views

Phase estimation algorithm: Modulo part in Nielsen and Chuang

In Nielsen and Chuang the explanation of phase estimation states: We have the following state: $$\frac{1}{2^{t/2}} \sum\limits_{k=0}^{2^t-1} e^{2 \pi i \varphi k}|k\rangle$$ Now we apply the inverse ...
5
votes
1answer
53 views

Why does Hamiltonian simulation seek to find the energy minimum, if eigenvalues of unitaries are always unimodular?

I know I am wrong here and trying to find out where I am making a logical mistake. I'd appreciate it if you can help me untangle. A. We know that the eigenvalues of Unitaries are all unimodular (...
1
vote
0answers
15 views

State of the art values for Shor algorithm depth and number of qubits on Clifford+T basis with arbitrary connectivity

I am trying to find the state of the art results in term of number of logical qubits and depth for the Shor factoring algorithm on the Clifford+T basis. I don't want to assume anything about the error ...
4
votes
1answer
108 views

Why is the function operator used in Simon's algorithm unitary?

From the Qiskit textbook I read about Simon's algorithm. There are two n-wide quantum registers, so the general state is given by $$|x\rangle_n|y\rangle_n$$ where x and y are the $2^n-1$ binary ...
1
vote
1answer
56 views

Trying to understand Grover's Algorithm

I'd like to start with saying sorry if my question makes no sense as I'm a physics student, but only in third year. I've discovered Grover's algorithm, but what I'm not sure of is if it could be used ...
3
votes
1answer
62 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 ...
1
vote
1answer
52 views

Generalizing the circuit for quantum teleportation for $n$-qubit states? [duplicate]

So the usual quantum circuit I know for quantum teleportation allows for the teleportation of the state on a single qubit, in the following way: How easy is to generalize this algorithm to allow for ...
3
votes
0answers
20 views

Are there direct usefull applications of the quantum Fourier transform not requiring heavy other subroutine

I know that the quantum Fourier transform has many applications such as order finding (which is used in Shor algorithm), phase estimation, etc. However those algorithms require extra subroutines which ...
2
votes
1answer
48 views

How is the "space time volume" defined?

In some papers such as this one the "space time volume" of an algorithm implementation is provided. However I am struggling to find a precise definition of that. How is such quantity defined ...
2
votes
1answer
61 views

SWAP test and density matrix distinguishability

Let us either be given the density matrix \begin{equation} |\psi\rangle\langle \psi| \otimes |\psi\rangle\langle \psi| , \end{equation} for an $n$ qubit pure state $|\psi \rangle$ or the maximally ...
6
votes
0answers
129 views

Review paper on depth, qubits and $T$ gates number on Clifford+T decomposition for various "typical" algorithms

My question I am looking for some review paper, or a list of different papers providing concrete numbers about the depth, number of qubits and number of $T$ gates required on the Clifford+T basis for ...
7
votes
3answers
690 views

Quantum advantage with only Clifford gates (Gottesman Knill theorem)

Let's say I want to solve a computational task which input can be encoded in $n$ bits of information. The look for a quantum advantage is (usually) asking to find a quantum algorithm in which there ...
3
votes
1answer
82 views

Conditional lower bound on approximate stabilizer rank of magic states

I am currently reading about the approximate stabilizer rank and properties of the same. I will quote the definitions from this paper. The stabilizer rank of a quantum state $|\psi\rangle$ is the ...
1
vote
1answer
86 views

How does a quantum computer execute a process by leveraging superposition?

I understand in plain terms superposition and entanglement, but I'm very unclear how either of these could work as a means to increase computation power. A helpful metaphor is that of the maze. A ...
3
votes
1answer
68 views

How to implement a quantum array

I'm trying to implement a quantum array. That is one that stores qubits and can be indexed via qubits. I can create one that handles setting values fairly easy. Have two registers, one for the ...
2
votes
0answers
53 views

What is the algorithm for the optimal decoder in a quantum erasure channel?

I'm reading this paper : Holographic Quantum Error Correcting Codes and on page 3 they describe an optimal decoder for erasure channel. The description is for CSS codes but they claim that "it is ...
4
votes
0answers
68 views

Oblivious Amplitude Amplification & Eigenstate decomposition

Looking at the oblivious AA (OAA) : https://docs.microsoft.com/en-us/azure/quantum/user-guide/libraries/standard/algorithms I am trying to figure out the eigendecomposition of Q, which leads to below. ...
9
votes
1answer
133 views

What does the paper "Training Variational Quantum Algorithms Is NP-Hard (Phys. Rev. Lett. 127, 120502)" mean?

I have seen the recent paper "Training Variational Quantum Algorithms Is NP-Hard (Phys. Rev. Lett. 127, 120502)" and the authors stated that training the classical optimization in ...
2
votes
2answers
253 views

What is the circuit for grover's algorithm if N is not a power of 2?

From the literature it seems that grover's algorithm works if $N$ is not a power of $2$. For instance, https://en.wikipedia.org/wiki/Grover%27s_algorithm and https://arxiv.org/abs/quant-ph/0005055 I ...
0
votes
0answers
22 views

Matrix derivation from prepare+ /select/prepare operator

Looking at the paper : https://arxiv.org/abs/2002.11649 and struggling to show $$ U_{A}=\left(U_{\mathrm{PREP}}^{\dagger} \otimes I_{n}\right) => \left[U_{A}\right]_{\mathcal{B}_{j}}=\left(\begin{...
3
votes
1answer
96 views

Implement the classical shadow coding error?

I'm trying to reproduce the basic method of classical shadow, which is based on the tutorial of pennylane. However, I've met some realization problems here when I finish reading the tutorial of ...
3
votes
1answer
95 views

Why are all the eigenvalues of a "Hermitian block-encoding" equal to $\pm1$?

I was looking at the paper : https://arxiv.org/abs/2002.11649 and the eigenvalue discussion is not clear to me. Block-encoding is a general technique to encode a nonunitary matrix on a quantum ...
2
votes
1answer
36 views

How do we ensure that the states input to a quantum algorithm are what we want them to be?

In various quantum algorithms like quantum Fourier transform we see that our input states are forced to be specified states. But we know that the main property of quantum computers is that the state ...
2
votes
1answer
63 views

What is quantum advantage truly?

Let's consider the Deutsch Jozsa algorithm, I understand that the superposition principle in quantum mechanics, helps us design circuits which would give answers in one single query. But then I would ...
1
vote
1answer
44 views

References about deriving the complexity of a given algorithm

Trying to learn about how to derive (& intuition) the complexity for a given algorithm as shown below. If there is any good reference or starting point that anyone can suggest that will be highly ...
1
vote
0answers
27 views

What is the relationship between the mixing operators and initial states found in QAOA and Quantum Annealing?

In many papers, the QAOA is shown to be intimately related to Quantum Annealing/Quantum Adiabatic Algorithm/Adiabatic Quantum Optimization. The mixing operator in the QAOA is described by Hadfield as ...
1
vote
1answer
25 views

Derivation of the state after applying $U_f$ in the Deutsch–Jozsa algorithm

On page 35 in Nielsen and Chuang, it's said that for the following quantum circuit implementing the general Deutsch–Jozsa algorithm: Next, the function $f$ is evaluated (by Bob) using $U_f$, giving $$...
2
votes
1answer
29 views

Is quantum query complexity equivalent to the total number of calls to the quantum computer for any given algorithm?

In other words, if an algorithm requires N total calls to the quantum computer to find the solution (of any given problem), would N be equivalent to its query complexity?
2
votes
0answers
75 views

Why is the first register of $|x,y\oplus f(x)\rangle$ called "data" register?

When talking about quantum parallelism, in Nielsen and Chuang, it's said that: it is possible to transform this state into $|x, y \oplus f(x)\rangle$, where $\oplus$ indicates addition modulo 2; the ...
2
votes
1answer
52 views

In block encoding, how to determine the dimension of the elements from $\alpha(⟨0|^{\otimes a}\otimes I)U(|0〉^{\otimes a}\otimes|\psi〉)=A|\psi〉$?

The block-encoding framework shows the following statement in general, as discussed in the paper https://arxiv.org/abs/1804.01973. A block-encoding of a matrix $A \in \mathbb{C}^{N \times N}$ is a ...
0
votes
1answer
37 views

Derivation of the effect of the Hadamard transform on a state |x⟩ in the Deutsch–Jozsa algorithm

On pg. 35 of Nielsen and Chuang, there's the following paragraph: By checking the cases $x=0$ and $x=1$ separately we see that for a single qubit $H|x\rangle=\sum_x (-1)^{xz}|z\rangle/\sqrt{2}$. I'm ...
0
votes
1answer
65 views

How to calculate the approximation ratio of QAOA?

In order to evaluate the QAOA circuit, we need to compute the approximation ratio, which is the expectation value of QAOA circuit divided by the best solution. My question is, how to find the best ...

1
2 3 4 5
16