Tag Info

Hot answers tagged algorithm

22

TL;DR: This is probably going to be disappointing. If a cat enters a superposition and we lose track of the relative phase $\phi$ then there is only one deterministic operation that returns to the $|\text{alive}\rangle$ state: the state preparation channel. In other words, we have to get a new cat. Let us represent the states of the cat on the Bloch sphere ...

5

2-local forms As I have seen the term, 2-local Hamiltonians are those Hamiltonians $\hat H$ which can be written as a sum of independent qubit operators $\hat H = \sum_i \sum_j \hat O_{ij}$, where each $\hat O_{ij}$ acts non-trivially only on two qubits $i$ and $j$. This is as opposed to a global Hamiltonian, whose terms may act on any number of qubits. This ...

3

I think the algorithm class you are referring to is EQP (Exact Quantum Polynomial-Time). There is a famous breakthrough paper by Ambainis that shows for a superlinear advantage between exact quantum algorithms over their classical counterparts (classical deterministic algorithms) for the query complexity of a total Boolean function. Later Ambainis, Iraids ...

3

Numbers from $0$ to $2^n-1$ are exactly what one can encode into $n$ bits or $n$ qubits using standard binary positional number system. The mapping looks like this \begin{align} &0\dots000 \mapsto 0 \\ &0\dots001 \mapsto 1 \\ &0\dots010 \mapsto 2 \\ &0\dots011 \mapsto 3 \\ &0\dots100 \mapsto 4 \\ &0\dots101 \mapsto 5 \\ &\ \ \... 3 As mentioned above there is nothing called "Oracle free" algorithm. Let's put this in simple words: Consider we are making a problem solving algorithm to solve the roots of a quadratic equation. Let the equation be ax^2+bx+c and the algorithm finds the values of x . Here the function to create ax^2+bx+c acts as an oracle. You can put this ... 2 This is due to how the \mathbf{A} matrix was defined; from that same tutorial page we have:\tag{1} \mathbf{A} = \sum_{n} c_n A_n $$where each A_n is unitary and c_n is complex (and in the original VQLS paper they further impose \lVert {\mathbf{A}}\rVert<1 and bounded condition number) but \mathbf{A} is never required to be unitary. Therefore,... 2 Yes, this statement is true. If there are N possible items to check, the classical brute force method takes time O(N). Grover's search only takes time O(\sqrt{N}). More precisely, if you want to have a probability of at least 1-1/N, the classical algorithm has to check N possibilities. The quantum algorithm has to perform$$\left\lfloor\frac{\pi}{4\...

2

Overview The short answer is no you cannot prepare this state efficiently; but, infact your question is a special case of a more general case I prove below which I will outline first as it applicable to a more general audience. After I will show that your question is indeed a special case of theorem. Finally, I will address the comments under your original ...

2

It is an implementation of a balanced oracle. However, the whole point of the Deutsch-Jozsa oracle is that you should not know in advance which oracle is being used. If you know the oracle, you'd already know the answer! Furthermore, the whole interest in Deutsch-Jozsa as compared to Deutsch is the scaling, i.e. wanting to be able to use oracles with an ...

2

TLDR: These formulas have nothing to do with each other. The first one is the definition of the Hadamard gate, the other one the state we're left with after having applied $f$. In the latter, the $z$ comes from the application of the Hadamard gate. These formulas are not linked. The first one simply describes that, for a single qubit state $|x\rangle$, we ...

1

First of all, if we write down $\left|\psi_1\right\rangle$, we get: $$\left|\psi_1\right\rangle=\frac{1}{\sqrt{2}^n}\sum_x|x\rangle\left[\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right].$$ Applying $f$ on this state gives us: $$\left|\psi_2\right\rangle=\frac{1}{\sqrt{2}^n}\sum_x|x\rangle\left[\frac{|f(x)\rangle-|1\oplus f(x)\rangle}{\sqrt{2}}\right].$$ Note that ...

1

The query complexity is usually spoken about with respect to an oracle or black-box function. It is the numbers of times you make use of that oracle in your algorithm (each time you use it, you are said to be "querying it", hence the terminology "query complexity"). It might be that you use the oracle many times in a single run of the ...

1

$U$ can be written as: $$U=\begin{pmatrix}\frac{1}{\alpha}A&B\\C&D\end{pmatrix}$$ while $|0\rangle^{\otimes a}\otimes|\psi\rangle$ can be written as: $$|0\rangle^{\otimes a}\otimes|\psi\rangle=\begin{pmatrix}|\psi\rangle\\0\end{pmatrix}$$ We thus have: $$U\left(|0\rangle^{\otimes a}\otimes|\psi\rangle\right)=\begin{pmatrix}\frac{1}{\alpha}A&B\\C&... 1 As hinted in the highlighted text, E_T arises from the normalization factor A(\tau). Specifically, differentiating (1), we get two terms$$ \begin{align} \frac{\partial|\psi(\tau)\rangle}{\partial\tau} &= \frac{\partial}{\partial\tau}\left(A(\tau)e^{-H\tau}|\psi(0)\rangle\right) \\ &= \frac{\partial A(\tau)}{\partial\tau}e^{-H\tau}|\psi(0)\...

1

For this answer it is important to know what the quantum counting algorithm is based on. To understand this algorithm, it is important that you first understand both Grover’s algorithm and the quantum phase estimation algorithm. Whereas Grover’s algorithm attempts to find a solution to the Oracle, the quantum counting algorithm tells us how many of these ...

1

Here are two more papers that may be of interest: A Quantum Algorithm For Linear PDEs Arising In Finance Dynamic Portfolio Optimization with Real Datasets Using Quantum Processors and Quantum-Inspired Tensor Networks

1

In a similar way to how the global phase difference of a state makes no physical difference, neither does amplitude of a state. We normalise states to have unit magnitude for mathematical convenience in the same way we don't carry around an $e^{i\phi}$ factor for arbitrary $\phi$ with all our states. This is because having unit vectors means we don't need to ...

Only top voted, non community-wiki answers of a minimum length are eligible