New answers tagged

0

First, you need to get familiar with the notion of classical complexity and big-O notation. For this, I recommend: MIT 16.070 Big O notation lecture notes Computational Complexity: A Modern Approach The Complexity Zoo and links in the See Also section. After getting a good grasp about classical complexity theory, you can start diving into quantum ...


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


0

You can try any way as both of them provide good results. The NumpyMinimumEigensolver is a slow and classical way to find the total ground state in the context of the question you are working on. The results of the NumpyMinimumEigensolver may differ from a purely classical one by a small factor. But, in reality, it is hard to find the exact and perfect ...


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


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


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


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)\...


0

The answers above say that interference, entanglement, and superposition are the reasons for a quantum computer being faster. While this is not wrong, it is not the full story either. Stabiliser computation, which starts with a $|0...0\rangle$ basis state and then applies Clifford operations to it, before measuring it in the computational basis, heavily ...


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


0

It is true for the electronic structure Hamiltonian you have written - $$ H_{\rm{fer}} = \sum h_{pq}a_p^\dagger a_q + \sum h_{pqrs} a_p^\dagger a_q^\dagger a_r a_s $$ because this $H_{\rm{fer}}$ is explicitly restricted to two-body interactions, and thus a quartic $O(n^4)$ number of terms. All the qubit mappings we use map each term to a constant $O(1)$ ...


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


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

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


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


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


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


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


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


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 \\ &\ \ \...


Top 50 recent answers are included