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
0
votes
0answers
6 views

Oracle with multiple solutions, Grover's Algorithm- Qiskit

Using qiskit, I want to build an oracle with multiple solutions. I am planning to use 10qubits. I don't know if i'm doing it right but where it goes: ...
0
votes
0answers
5 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 ...
0
votes
1answer
34 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 ...
2
votes
1answer
38 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 a IBMQ backend can be passed into the function as a Quantum ...
1
vote
1answer
38 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
18 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 ...
1
vote
1answer
37 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
53 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
124 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 ...
6
votes
3answers
660 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
79 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
78 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
62 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
52 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 ...
3
votes
0answers
46 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
121 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
242 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
87 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
88 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
33 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
57 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
42 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
21 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
22 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
27 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
74 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
49 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
35 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
52 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 ...
3
votes
1answer
160 views

What are quantum algorithms with only one possible outcome with probability equal to one?

I would like to study circuits with only one possible outcome. Quantum phase estimation, Bernstein-Vazirani, and in part Deutsch-Jozsa (for constant functions) come to mind - do you know any other ...
1
vote
1answer
61 views

Wick rotation of the Schrödinger equation

Studying the following paper: https://www.nature.com/articles/s41534-019-0187-2.pdf Trying to figure out how $ E_T$ shows up from (1) and (2). Any suggestion or guidance would be appreciated. We ...
1
vote
1answer
24 views

Is this a valid implementation of the balanced Deutsch-Jozsa oracle

Is it correct to implement a balanced Deutsch-Jozsa oracle by CNOTing the first qubit with the last one (the ancilla qubit), it would get you a balanced output. And if it's valid why is it not ...
0
votes
1answer
43 views

How is Grover's algorithm used in reducing duration of time taken to brute-force a hash? [duplicate]

I read somewhere on internet that brute-forcing a hash on classical computer will take time proportional to the length of data. But somehow if one have possible inputs used, using Grover's algorithm, ...
2
votes
1answer
88 views

Does the input of the quantum counting algorithm have to be a uniform superposition state?

Will the quantum counting algorithm work if the input is not a uniform superposition (even not a superposition of all basis states)? For example, if I use a state such as : $$\frac{1}{4}(2\vert 0000\...
14
votes
1answer
4k views

How can we keep Schrödinger's cat alive?

We know, Schrödinger's cat inside the box is in the equal superposition state of both alive and dead. We can express its state as $$|\text{cat}_\phi\rangle= \frac{|\text{alive}\rangle+e^{i\phi}|\text{...
2
votes
1answer
78 views

Do VQE and QAOA use the same Hamiltonian?

In this paper, it talks about the 2-local Hamiltonian in the form: $H = \sum_{(u,v)\in E} H_{uv} + \sum_{k \in v} H_k $ It also says the Ising model, Heisenberg model, XY model and QAOA are in the ...
3
votes
2answers
39 views

Normalization question in VQLS

I was studying VQLS in https://qiskit.org/textbook/ch-paper-implementations/vqls.html and run into the following normalization during the cost calculation. It says if $ |\Phi\rangle$ has a small norm....
2
votes
1answer
40 views

Reason for sending numbers from 0 to $2^n − 1$ in Deutsch–Jozsa algorithm

In Nielsen and Chuang, when talking about the Deutsch–Jozsa algorithm. The Deutsch’s problem is described as the following game. Alice, in Amsterdam, selects a number x from 0 to $2^n − 1$, and mails ...
0
votes
2answers
60 views

Why would matter if $f(0)$ equals to $f(1)$ in Deutsch’s algorithm?

I have a question on the following quantum circuit implementing Deutsch’s algorithm Why would matter if $f(0)$ equals to $f(1)$? Are they what changes the phase of the first qubit state from + to -? ...
0
votes
1answer
36 views

Trace calculation from the basis to |+> and |-> states

I was reading the paper; https://arxiv.org/abs/2002.00055 and going through some of the formulas below and I am a bit stuck between (1) and (2). How the equation (1) turns into (2) is not clear to me.....
4
votes
1answer
130 views

How to prepare a quantum state of the form $\frac1{2^{n/2}}\sum_{x \in \{0, 1\}^{n}} |x\rangle |y_x\rangle$ with $y_x$ random variables?

Let's say I am given an efficiently samplable probability distribution $D$, over $n$ bit strings. I want to efficiently prepare the following state \begin{equation} |\psi\rangle = \frac{1}{\sqrt{2^{n}}...
1
vote
0answers
87 views

What is the justification for the use of this arbitrary post-processing vector?

I am reading through this paper which describes the use of a post-processing vector $\vec{c}$ with elements having values of $(-1,0,1)$. In equation 3 they give their solution as a linear combination ...
1
vote
1answer
103 views

Does anyone have some references on EigenGate used in Google's cirq framework?

I am trying to understand the code below but can not find any references other than the code itself. https://github.com/quantumlib/Cirq/blob/v0.11.1/cirq-core/cirq/ops/eigen_gate.py I am not clear ...
1
vote
0answers
65 views

Quantum Circuits for Time-Series Data

I am currently working with a dataset with autocorrelated features, i.e, x(t) affects the value of x(t+1) which affects the value of x(t+2). Suppose this is the circuit representing x(t): Does ...
3
votes
2answers
81 views

Can we use reversible computation to construct oracle circuits?

One of the question while I discussed with my colleague in the math department was the construction of oracle circuit. In computer science, specifically in algorithm, we take oracle as granted and ...
1
vote
0answers
31 views

What's the importance of a relationship with Gibbs state in the context of VarQITE or variational algorithms?

Trying to figure out VarQITE or variational algorithm, I ran into the Gibbs state. What's the importance of a relationship with Gibbs state in this context. Why can we just use the arbitrary state ...
4
votes
1answer
71 views

Objective function of Quantum GAN in the paper "Quantum generative adversarial networks"

In this paper about Quantum GANs, the authors do not explain clearly how do they have the equation $$\newcommand{\tr}{\operatorname{Tr}}\newcommand{\Pr}{\operatorname{Pr}} V(\vec{\theta}_D, \vec{\...
3
votes
1answer
46 views

What are QHT, QWT and QFT?

I am new to quantum computing. I am not able to understand QHT, QWT and QFT. I tried searching for a suitable material but still could not find them. It would be great if someone can explain and also ...
2
votes
2answers
477 views

Is it true that the way we must program Quantum Computers is through Total functions only, if so why?

I have read that the way we must program Quantum Computers is through Total functions only. Why is this the case? Is it because quantum circuits are less forgiving in terms of logical errors? Could ...

1
2 3 4 5
16