5

There aren't many examples! The main reason for advantages in quantum computers is the ability to constructively combine amplitudes - if you've only got 1 qubit, there aren't any amplitudes to combine! The best use case I can think of is randomness. A quantum computer (implemented with arbitrary error) could theoretically be a near perfect source of entropy,...


4

A (wonderful) discussion of this problem can be found in Nielsen and Chuang (Sec. 6.1.4 Performance). The number of marked elements is labelled $M$ below (instead of $k$ in your case) and the emphasis is mine. tl;dr if you know $M \geq N/2$ then just randomly pick an item: this has a success probability at least one-half and only requires one call to the ...


4

Let's say that the first bit of $s$ $s_0=1$ (the argument will be exactly the same for any bit, just for convenience). You can split the space of inputs $x \in \{0,1\}^n$ in two halves: one half where $x_0 = 0$ and the other half where $x_0 = 1$. For each bitstring $x$ from the first half you'll have a bitstring $\tilde{x}$ from the second half which will ...


3

I think the closest thing to a "while loop" in a quantum algorithm is something like the Variational Quantum Eigensolver (VQE) or other classical-quantum hybrid algorithms. In these, a certain cutoff is defined for when the variational circuit is "close enough" to approximating the desired quantum state, so you can think of it as a while ...


3

To all intents and purposes, the double-slit experiment is the same as the Mach-Zehnder interferometer (a photon can go one of two paths before interfering at the output). Since the Mach-Zehnder interferometer implements Deutsch's algorithm, you could claim that the double slit experiment will do the same. Effectively, what you'd be talking about is by ...


3

Yes, there is an error in your logic. If you take the task one step further, to $N = 4$, the desired state is $\frac{1}{2}(|1000\rangle + |0100\rangle + |0010\rangle + |0001\rangle)$, and the state your solution prepares is $\frac{1}{\sqrt2}|1000\rangle + \frac{1}{2}|0100\rangle + \frac{1}{2\sqrt2}(|0010\rangle + |0001\rangle)$. You can see this for ...


2

The restricted gate set of, for example, $\{H,T\}$, is more relevant when you start talking about error corrected quantum computation. It may be that when you act on individual, physical, qubits, you can implement and arbitrary single-qubit rotation. However, when you encode in an error correcting code, and you want to implement a gate directly on the ...


2

In Qiskit, the iso() function allows you to add a gate, defined by means of a unitary, to your quantum circuit: https://qiskit.org/documentation/stubs/qiskit.circuit.QuantumCircuit.iso.html The decomposition used in the iso() function was introduced by Iten et al. in https://arxiv.org/abs/1501.06911. Of course this is related to the circuit, not to the ...


2

The remark that you state is absolutely critical. Let's try and introduce a notation that takes the spaces into account better. So, we're going to have a set of $a$ qubits denoted $C$, a set of $b$ qubits denoted $D$ and a set of $s$ qubits denoted $S$. Now I can use $U_{CS}$ to mean apply $U$ on qubits in sets $C$ (the ancillas) and $S$, and act as identity ...


2

Pretty much everything! Any Hamiltonian that you want to simulate from e.g. condensed matter physics, is highly likely to be sparse by virtue of the fact that interactions are local. Equally, any tensor product of Paulis is sparse. In terms of quantum computing, most gates that you choose to use tend to be sparse, the notable exception being something like a ...


2

Let's consider the following $4$ qubit state (taking $n=2$ from the quesion): $$|\psi_{in} \rangle = \frac{1}{2} \big( |0 0\rangle \otimes |00\rangle + |1 1\rangle \otimes |1 1\rangle + |01\rangle \otimes |01\rangle + |10\rangle \otimes |10\rangle\big)$$ The first two qubits are Alice's qubits and the last two qubits are Bob's qubits. We can describe this ...


2

I think you should look for quantum amplitude encoding strategies. A nice and practical tutorial (with reference to Qiskit) is the following one by Maria Schuld: https://medium.com/qiskit/building-the-worlds-smallest-quantum-classifier-7da7cd845b84 Interesting (but more advanced) articles are also: https://www.nature.com/articles/s41598-019-40439-3 https://...


2

Let's make a few observations first: Since an $N$-qubit stabilizer state can be generated starting from $| 0 \rangle^{\otimes N}$ and applying H, CNOT, and S gates, we make the following observations. By simply applying the Hadamard on all qubits, one can generate the state $ | + \rangle^{\otimes N}$ which is maximally coherent (under the free operations ...


2

If you pass a list of qubits instead of a list of register this works. For this do circ.append(oracle, train_register[:] + control[:]) where train_register and control are QuantumRegisters.


2

One option would be to identify an upper bound for the number of iterations of the while loop and implement a traditional and conditional loop: Consider you have three registers a control $|\text{cntl}\rangle$ bit some state $|\psi\rangle$ some condition for the while loop $|\text{cond}\rangle$ Assume the maximal number of iterations is bounded to $B$, ...


2

The way that many algorithms would deal with such a desire is to incorporate the measurement at a more fundamental level, essentially making it part of the 'while' condition. i.e. you have an output qubit that is 0/1 for computation complete or not, you measure it, and decide whether to continue or not. Because that's a bit of classical processing, it doesn'...


2

We can use the SWAP test to determine the inner product of 2 states $|\phi\rangle$ and $|\psi\rangle$. The circuit is shown below The state of the system at the beginning of the protocol is $|0\rangle \otimes |\phi \rangle \otimes |\psi \rangle$. After the Hadamard gate, the state of the system is $|+\rangle \otimes |\phi \rangle \otimes |\psi \rangle$. The ...


1

For quantum computing you will need some bases in linear algebra and probability theory. This book has pretty much everything you need to know about quantum information, and it covers the bases you need to understand the field, i.e. chapter 2 Introduction to quantum mechanics is about Linear Algebra and there is also a little bit of proba theory on the ...


1

Quantum Operations are visualized as Unitary matrices. This puts a limit to their sparseness. A Quantum Operation acting on $n$ qubits can be represented by Unitary Matrix of size $2^n \times 2^n$. However since these are unitary operations, every column of the Unitary must have $L2$ norm as $1$ and hence have atleast 1 non-zero value. This implies that out ...


1

This corresponds to the problem of counting the number of 1's in some $n$-bit input string. It is well known that for exact counting there can be no significant speedup. This follows from the $\Omega(n)$ lower bound on the quantum query complexity of parity (see here). For approximate counting you can get a quantum speedup, as is described here.


1

(I'm unsure if you were asking for a derivation of the inner product, but hopefully this is insightful). Let's call the set of target states $T$. Recognize that, because $|\omega\rangle$ is the equal superposition of $ M$ states, each of the marked bitstrings will have a coefficient of $ \frac{1}{\sqrt{M}} $. For clarity, we can write: $$ | \omega \rangle = \...


1

Basically, you divide the entire $7$-qubit Hilbert space into two subspaces: the one spanned by your state (let's call the state $|\psi\rangle$), let's call that subspace $W$, and it's orthogonal complement $V = W^{\perp}$. You want any vector from $V$, because this will by definition be orthogonal. We know that $P_{V}$ + $P_{W} = I$, with $P_{V}$ and $P_{W}$...


1

Firstly, you have to normalize your vector $x$ to have an Euclidian norm equal one, i.e. $$ ||x||=||(0,0.1,0.4,0.9)|| = \sqrt{0^2 + 0.1^2 +0.4^2+0.9^2} = \sqrt{0.98} $$ So, your vector representing a quantum state is $$ \frac{1}{\sqrt{0.98}}(0,0.1,0.4,0.9). $$ Now, you can apply methods described in this thread.


1

Considering a fixed set of universal gates has several advantages. As a broad principle, standardization has proven extremely useful in computer science. Choosing a fixed set of primitive operations - even if they aren't always the best ones for every possible specific application - allows everyone to be on the same page, which makes it easier to focus on ...


1

The author in that paper allows himself arbitrary angle single and two qubit gates. With this set it is generally pretty easy to exactly match a given unitary, since the two qubit gates can give you the backbone of the correct entanglement structure, and the single qubit gates can conjugate the gate into the exactly correct basis. The reason that accuracy ...


1

To get a quantum gate with single photons, you need something of the form: $$(|0\rangle+e^{i*0}|1\rangle)|1\rangle \rightarrow (|0\rangle+e^{i\pi}|1\rangle)|1\rangle$$ Putting this in English, it means that a second photon causes a phase shift in the first photon. This type of interaction can't occur simply by overlapping or interfering photons, but ...


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