People who code: we want your input. Take the Survey

New answers tagged

0

To answer your first question, whenever you run a QPE circuit on, let's say, $n$ ancilla qubits, you will be left with the binary representation of the phase $\theta$, encoded in the ancilla qubits. Measuring these ancillary qubits provides you an estimate of the phase $\theta$ (up to n-bit precision). Note, the probabilities of the states are there to ...


1

Oracles in quantum computing are "black boxes" that usually serve as input or help to another larger algorithm. They usually are defined by a function $f: \{0,1\}^n \rightarrow \{0,1\}^m$, which takes an $n$-bit input and produces an $m$-bit output. An important thing to note about oracles is that usually you don't know what is going on inside the ...


0

It means to find a basis for the Hilbert space that can be partitioned into singles and pairs of vectors which form one- and two-dimensional subspaces left invariant by the action of the projectors $\Pi_i$. More formally, a decomposition for the space means to write the (here Hilbert) vector space $\mathcal H$ as a direct sum of subspaces which are invariant ...


2

The IQPE procedure tries to reduce the extra number of ancilla qubits needed to measure the phase and replaces that with the extra number of iterations that we perform to measure our phase. Imagine you have the phase as $\theta = 0.\theta_{0}\theta_{1}\theta_{2}\theta_{3}$. So, what IQPE does is that in the first iteration, it tries to identify the value of $...


2

In QAOA you do not implement Hamiltonian $H$ itself but gate defined as $U = \mathrm{e}^{iHt}$. Since Hamiltonian $H$ is always Hermitian, operator $U$ is always unitary. You can see proof of this here. Concerning implementation of QAOA circuits, I would recommed this article. It contains discussion how to convert QUBO to Hamiltonian and in the appendix, ...


3

To summarize the relation in one line, the Hadamard Transform is essentially the Quantum Fourier Transform for the special case of a single qubit. Traditionally, the Quantum Fourier Transform $U_{FT}$ for $n$ qubits is defined as $$U_{FT}|x\rangle_n = \frac{1}{2^{n/2}} \sum_{y=0}^{2^n - 1} e^{2 \pi i x y / 2^n}|y\rangle_n$$ However, this is not really the ...


2

The original Amplitude Estimation algorithm (Brassard et al., 2002) uses Phase Estimation. So, it is OK to notice the similarity between them. Other approaches, however, have emerged in recent years that do not use PE for Amplitude Estimation like this and this.


2

To find the differences between them, you only need to know the aim of the problems. The aim of AA is to find the answers from unstructured data(or more directly, amplify the probability of the right answer). The aim of PE is to find the phase, more specifically the $\phi$ in the book of Nielsen: Suppose a unitary operator $U$ has an eigenvector $\mid u\...


1

If I were you, I'd ignore the matrix $R$ and instead work with the matrix $Q$. They give you a conversion between vectors in the two different representations. First, I'm going to simplify things a bit by working with $$ \tilde Q=\left(\begin{array}{cc} e^{i\phi/2} & 0 \\ 0 & e^{-i\phi/2} \end{array}\right)Q. $$ You'll have to compensate for this in ...


3

how one evaluation of $U_f$ on $\left|+^n\right>$ only requires one query of our black box $f$ It doesn't. There are two black boxes. The quantum black box $U_f$ is the quantum counterpart of the classical black box $f$. In analyzing the query complexity of the classical search algorithm we count the number of times the algorithm invokes the classical ...


3

Disclaimer: I've mainly worked on Symmetric Cryptography. Hence, not only is my answer likely to be incomplete, but an answer concerning assymetric cryptography would be appreciated. Most of the attacks giving an exponential speedup on symmetric cryptosystems use Simon's algorithm. Such attacks have been observed for instance on: the Even-Mansour scheme (...


3

Vidal proved that, pure-state quantum computation is efficiently simulable classically if the quantum computer’s state at every time step has amount of entanglement (measured by Schmidt rank) polynomially-bounded (theorem 1 in the linked paper) And if the amount of entanglement grows subexponentially, then it can be classically simulated with sub-exponential ...


1

The short answer to your first question is no, there is no "single standard" of representing circuits in terms of text/language. The closest to a "single standard" of representing circuits visually is the qiskit and cirq draw functions which produce very similar results that are basically standard in format . Due to the fact that no ...


1

The state on which the Fourier transform is being performed is defined in the paper as $$|\Psi_2\rangle\propto \sum_{m=0}^{P-1}\sin[(2m+1)\theta]|m\rangle=\sum_{m=0}^{P-1}\sin\left[2\pi f\frac{m}{P}+\pi\frac{f}{P}\right]|m\rangle\equiv\sum_{m=0}^{P-1}x_m|m\rangle.$$ We can compare this to the definition of a discrete Fourier transform with period $f$: $$X_f=\...


0

As far as I know there isn't a "once size fits all" algorithm, rather random bench-marking is performed to have a statistical accuracy of the gates your computer has. There wouldn't be much point to make it just as short as possible since you would ideally try as many times as you can your gates to get an accuracy for your computer.


0

Given that $\mathcal{A}$ is a unitary matrix, $\mathcal{A}^{-1} = \mathcal{A}^*$ $$ \begin{aligned} \mathcal{A}S_{0}^{\phi}\mathcal{A}^{-1}|Y\rangle = & \mathcal{A}(I - (1-\phi)|0\rangle\langle0|)\mathcal{A}^{-1}|Y\rangle \\ =& |Y\rangle - (1-\phi)\mathcal{A}|0\rangle\langle0|\mathcal{A}^{-1}|Y\rangle\\ =& |Y\rangle - (1-\phi)\mathcal{A}|0\...


0

OK, my question has some suspicious implicit assumptions. Usually the point of the algorithm is not to prepare a given state $|B\rangle$ from an initial state $|A\rangle$. If $|B\rangle$ encodes the solution to a problem, and if we know $|B\rangle$ right from the start there no need to build an algorithm. Rather, the problem usually is to construct a state $|...


1

Just few ideas, I do not pretend this to be the definitive answer. Firstly, to exploit quantum advantage, you need to employ both superposition and entanglement. If these phenomena are not employed, a quantum computer can do anything a classical one can do but with no speed-up (I supposed that e.g. Toffoli gate is implemented in the computer, so you can ...


1

A few thoughts: If you identify a few of the axes of an $n$-qubit state space, those corresponding to bit-strings $|s_1,...,s_n\rangle, s_i\in\{0,1\}$, with "classical states", then it might seem natural to say that "quantum algorithms are allowed to take shortcuts". But I think this picture is actually faulty. When you say this, you are ...


0

A major problem with implementing a hash set on a quantum computer is that, if you are inserting a superposed item, it can go into a superposition of buckets. But if you don't operate on a bucket, you can't possibly have inserted an item into it. Therefore to insert (or query) a superposed item correctly, which goes into a superposition of all the buckets, ...


2

Probably the easiest way to understand this is to pretend that the mixer is NOT there and see what happens. So, let's assume you have some initial state $\lvert \psi \rangle = \sum_x \psi_x \lvert x \rangle$ and you want to use QAOA to find the ground state of some cost Hamiltonian $H_C$. I'm using the notation $\big\{\lvert x \rangle : x \in \{\pm 1\}^n \...


3

The state is indeed entangled. The parenthesis should include the $|f(x)\rangle$ factor in the equation (otherwise, what would the $x$ in $f(x)$ mean?).


1

CW from Self-Answer I asked this question a while ago, and I've learned I think a little bit about many of the outstanding open problems in the field, and more about science communication in general. Of course I suspect generally most in the QC community want to have the problems that they work on be accessible to a broader audience. And there are, from my ...


Top 50 recent answers are included