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

If you look at the formula you want to prove term-by-term, you'll notice that the sum and the $(-1)^f(x)$ part is the same in both formulas; you just need to show that $$H^{\otimes n} |x\rangle = \frac{1}{\sqrt{2^n}} \left( \sum_{y=0}^{2^n-1} (-1)^{x \cdot y} |y\rangle \right )$$ You can either show this strictly by induction (similar to this question but ...


4

To answer your first question, the quantum oracles are defined by their effect on the basis states $|0\rangle$ and $|1\rangle$, and if the oracle has to be computed on a superposition of basis states, its effects are expressed using the fact that the oracle is a linear transformation. This means that you never compute $f(|+\rangle)$; instead, to compute the ...


4

Your first formula is not correct. The correct formula for Hadamard gates for the arbitrary $|x\rangle$ from the calculational basis is (it can be proved by induction): $$H^{\otimes n}|x\rangle=\frac{1}{\sqrt{2^n}} \sum_{y=0}^{2n-1}{(-1)^{x\cdot y}}|y\rangle$$ where $x\cdot y=x_0y_0\oplus x_1y_1\oplus x_2y_2\oplus ...\oplus x_ny_n$ In case $|x\rangle = |0\...


4

It is limited to matrix $U_f$ which maps $|x,y\rangle$ to $|x,y\oplus f(x)\rangle$, and the little thought is $$U_f|x,-\rangle=\frac{1}{\sqrt{2}}(|x,0\oplus f(x)\rangle-|x,1\oplus f(x)\rangle)=$$ $$=\begin{cases} |x,-\rangle & \text{if }f(x)=0\\ -|x,-\rangle & \text{if }f(x)=1 \end{cases}=(-1)^{f(x)}|x,-\rangle$$ where $x\in\{0,1\}$ or generally $x\...


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

Here the subscripts are of the form $1i$, where $i$ is the label of the subsystem (recall that you are using two qubits for this $\left|\psi\right>_0=\left|00\right>_{1}$). So any product of subscripts can be written as $\left|q_0\right>_{10}\left|q_1\right>_{11}=\left|q_0q_1\right>_{1}$ with $q_0,q_1\in\{0,1\}$ in this convention, which makes ...


3

One implements $U_f$ with one circuit that acts on qubit(s) in the superposition state. This means that no matter what is the input (basis state in the superposition), we act on the qubits with the same circuit and it takes the same execution time (the same number of gates in the circuit) for all possible inputs. So, how I understand, the scenario of ...


3

I have implemented via qiskit two algorithms and posted in github that need only 1-2 qubits. First is Iterative Quantum Phase Estimation (IQPE) that works on two qubits, the second one is Variational Quantum Eigensolver (VQE) that works on only one qubit (one can do also for 2 qubits) in my implementations. Actually they are jupyter notebook tutorials, so I ...


3

Probably only two qubits constrain set of algorithm you can run on your device, for example HHL algorithm (linear equation solver) seems to impossible work there. You can however implement algorithms based on uniformly controlled rotation used for preparing arbitrary quantum state. See details in the paper Transformation of quantum states using uniformly ...


3

To measure, observe that you are simply projecting a quantum state onto some basis set of vectors. First, I will note that this state is not normalized. Let us first define the following quantum state. $$|\psi_i\rangle = \begin{pmatrix}1\\-1\\0\\0\end{pmatrix}.$$ Then, calculating the corresponding probability yields: $$|\langle \psi_i|\psi_i\rangle|^2 = (...


3

Yes, it will depend on $n$ because sampling with replacement is assumed in the proof, which doesn't make sense if $n$ is finite. Intuitively, if a function $f$ really is balanced, and first output corresponding to certain random input is $0$ or $1$, then the probability that the second output corresponding to some other random input will be the same is less ...


3

@cgranade and I have a chapter on the Deutsch-Jozsa algorithm (Chapter 7) as well as implementations of the oracles for Q# in our book Learn Quantum Computing with Python and Q#. You can find the code samples for the book in the repo here. In particular, the oracles look like this: namespace DeutschJozsa { open Microsoft.Quantum.Intrinsic; ...


3

I think this snippet from Cirq's Deutsch's algorithm example (disclosure: I am its author) should be fairly easy to understand: def make_oracle(q0, q1, secret_function): """ Gates implementing the secret function f(x).""" # coverage: ignore if secret_function[0]: yield [CNOT(q0, q1), X(q1)] if secret_function[1]: yield CNOT(...


3

Deutsch's algorithm is not faster on a quantum computer, Deutsch's algorithm is only possibe on a quantum computer. A classical computer cannot perform Deutsch's algorithm, a classical computer can only simulate Deutsch's algorithm. Forget about speed, more fundamental is that we are performing a type of computation that can never be performed, in any ...


3

This is not so straightforward, I suspect. The issue is being able to distinguish between the constant case (e.g. every input gives output 0) and the case where only one input returns 1, and all others return 0. To distinguish these cases is essentially a Grover Search (the return of 1 being essentially a marked item that you want to search for the existence ...


2

There are really two different questions here. How can you figure out that a given output can be written as tensor product of two vectors? This is equivalent to asking: how do you figure out whether an output is separable? For pure states, which is what you are considering, this is rather easy. In your specific case (two qubits), you might simply notice ...


2

If you have already got, mathematically, to the point of having the vector $(1,-1,1,-1)/2$, you don't have to worry about the action of the controlled-not any more. You've already done that! All you have to do is factor the answer. Personally, I usually find the answer quite difficult to see when expressed in this way. Once you've got the answer you can ...


2

I will try to give an answer from complexity theory's point of view. This question should be asked in cs.stackexchange by the way. The Deutsch-Jozsa problem has an efficient algorithm on quantum computation and on a classical probabilistic Turing machine, so it is in BQP and BPP. There is no result that says: if you show a problem A in BQP and not in P, then ...


2

On a classical computer, you can recycle memory, so there is no need for storing all intermediate results. The main source of the higher performance of quantum computers is the possibility to do an operation with all different values you can store in n q-bits register at once. However, this is not a case always. For example, the evaluation of Boolean ...


2

This picture can be confusing, since it makes some assumptions that are not clear when you quickly scan through the text. The picture of the oracle $U_f$ describes its effect on the basis states that go into it, not on arbitrary superposition states. If both $x$ and $y$ are basis states, the oracle will behave exactly as the rectangle says, but the ...


2

CNOT gate is an example that implements a balanced function for which $f(0) = 0$ and $f(1) = 1$: \begin{equation} CNOT \frac{1}{2}\left(|0\rangle + |1\rangle \right) \left(|0\rangle - |1\rangle \right) = \\ = \frac{1}{2}|0\rangle \left(|0 \oplus f(0)\rangle - |1 \oplus f(0)\rangle \right) + \frac{1}{2}|1\rangle \left(|0 \oplus f(1)\rangle - |1 \oplus f(1)\...


2

You start with a polarisation filter. This does nothing to the path of your photon and, effectively, measures the polarisation of the photon, meaning that you prepare the "second" qubit in the fixed state determined by what polarisation the filter is detecting. So, at this point, you have $$ |0\rangle|-\rangle $$ Then, you input to a beamsplitter. ...


1

Let's see how to get from $ |\psi_{c}\rangle = \frac{1}{2}(|0_{1}f(0_{2})\rangle -|1_{1}f(1_{2})\rangle -|0_{1}\tilde f(0_{2})\rangle +|1_{1}\tilde f(1_{2})\rangle ) $ to the case of $ f(0)=f(1) $: $$\frac{1}{2}(|0_{1}f(0_{2})\rangle -|1_{1}f(1_{2})\rangle -|0_{1}\tilde f(0_{2})\rangle +|1_{1}\tilde f(1_{2})\rangle ) = \\ = \frac{1}{2}(|0_{1}f(0_{2})\...


1

This is not an full answer to your question. But I am very interested in how did you build your own 2-qubit device, as I am thinking about such a project for some months now. Would you mind to get in touch with me and exchange our thoughts on this? I would really love to get into discussions with you, maybe you could support me to build my own device? ...


1

Stephan Jordan maintains a very comprehensive list of quantum algorithms on https://quantumalgorithmzoo.org/. Now that you have worked on some famous ones, you can consider veering off a bit. Take a look at the "Algorithm: Machine Learning" consolidation section. There are for instance single-qubit and two-qubit classifiers that could be interesting. In ...


1

I implemented them as a "subcircuit" so it looks "hidden" from the "outside". constant 0: input = QuantumRegister(1, name='input') temp = QuantumRegister(1, name='temp') constant0 = QuantumCircuit(input, temp, name='oracle') oracle = constant0.to_instruction() identity: input = QuantumRegister(1, name='input') temp = QuantumRegister(1, name='temp') ...


1

An oracle $U_f$ is actually $\mathrm{X}$ gate (or a negation). The circuit implementing the oracle is following Qubit $q_0$ is input and qubit $q_{1}$ is output. Firstly $\mathrm{X}$ is applied on $q_{0}$. This negate the qubit, however, we want to have an output on $q_1$. Therefore, we apply $\mathrm{CNOT}$ which in this setting "copy" the $q_{0}$ to ...


1

The $(-1)^{x\cdot y}$ terms come from the matrix elements of $H^{\otimes n}$. To see this, start from considering the matrix elements of $H$. You can check that they can be written as $H_{ij}=(-1)^{ij}$ where $i,j\in\{0,1\}$. The matrix elements of $H^{\otimes n}$ are indexed by tuples of $n$ binary numbers, that is, writing $I\equiv (i_1,...,i_n), J\equiv(...


1

Indeed, the formula assumes that $n=\infty$, and is approximately correct if $2^n \gg k$


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