Questions tagged [deutsch-jozsa-algorithm]

The Deutsch–Jozsa algorithm is a quantum algorithm, proposed by David Deutsch and Richard Jozsa in 1992. Although of little practical use, it is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. It is also a deterministic algorithm, meaning that it always produces an answer, and that answer is always correct. (Wikipedia)

Filter by
Sorted by
Tagged with
1
vote
2answers
62 views

How can a half-wave plate affect the position qubit and not the polarization qubit of a photon?

I recently was watching these 2 videos on Coursera which show how to build a simple quantum computer that can implement the simplest case of the Deutsch-Jozsa algorithm (which uses only 2 qubits). ...
2
votes
2answers
176 views

Question about DIY Quantum Computer Prototype

I recently came across these 2 videos on Coursera which show how to build a simple quantum computer that can implement the simplest case of the Deutsch-Jozsa algorithm (which uses only 2 qubits). ...
1
vote
1answer
42 views

Hamming Weight algorithm

Is there any quantum algorithm that can improve a calculation time for determining the Hamming weight of an arbitrary bit string? The Deutsch-Jozsa algorithm seems like it would be useful for this ...
3
votes
2answers
51 views

Example of a quantum algorithm better than its classical counterpart which involves only $1$ qubit?

I was reading over the proof of the Deutsch-Jozsa algorithm, which in its simplest case, involves at least 2 qubits. Is there an example of a quantum algorithm that is better than it's classical ...
2
votes
1answer
36 views

Why is the function $f_s(x)=\sum_i x_i s_i \pmod 2$ balanced?

A parity function $f_s:\{0,1\}^{n}\rightarrow\{0,1\}$, for some $s\in \{0,1\}^n$, is a function of the form $f_s(x) = x \cdot s$, where the inner product is taken modulo 2. Show that $f_s$ is a ...
3
votes
1answer
89 views

Deutsch's algorithm in Qiskit

I am trying to understand and implement the Deutsch algorithm. I follow the logic from Nielsen book and I started to implement it in Qiskit. For implementing the oracle, I use a CNOT gate and now I ...
3
votes
5answers
145 views

Any other quantum algorithms than Jozsa-Deutsch decision algorithm, Grover search algorithm, Shor factorization algorithm?

I have been working on implementing Jozsa-Deutsch decision algorithm, Grover search algorithm, Shor factorization algorithm on my home-made 2 qubits device. I am wondering if there are any other ...
0
votes
1answer
52 views

How are the two states factored out of Deutsch's circuit?

After placing the Hadamards on the 2 qubits (both initialized in the $|1\rangle$ state) in the circuit, we are given: $ |\psi_{b}\rangle = \frac{1}{2}(|0_{1}0_{2}\rangle -|1_{1}0_{2}\rangle -|0_{1}...
5
votes
1answer
767 views

How does an oracle function in Grover's algorithm actually work?

I have lately been studying quantum algorithms. I have gone through the Deutsch algorithm and Grover's algorithm. There's always a function in the oracle which somehow 'recognizes' the solution ...
1
vote
1answer
59 views

Understanding the working of oracle in Deutsch - Josza Algorithm

Reading through the official Qiskit textbook, I fell onto the problem of Deutsch - Josza Algorithm, which seemed little mystical to me at first but as I tried out the example of its working, I was ...
4
votes
4answers
227 views

Implementing four oracles for the Deutsch Algorithm (preferably on IBM Q Experience)

I guess, I understood simple Deutsch Algorithm (if unary function is balanced or constant) as described here: Introduction to quantum computing: The Deutsch algorithm I need to test it. I was ...
2
votes
1answer
57 views

What happens with the oracle $U_f$ if you have different blackbox execution times for different inputs?

What will happen if the 'blackbox' function $f$ in Deutsch's algorithm is designed in such a way that it takes millions of years to deliver result if input is $x = 1$ and few seconds if the input is $...
3
votes
1answer
62 views

How does $U_f$ in Deutsch's Algorithm affect the state $|x\rangle$?

I am trying to read Nielsen's and Chuang's book on quantum computing and I am having problem understanding Deutsch's algorithm. According to my understanding of the algorithm, the state $|x\rangle$ ...
2
votes
1answer
84 views

Understanding Steps in Deutsch's Algorithm

I am currently working my way through the book Quantum Computation and Quantum Information by Chuang and Nielsen. So far it has been a joy to read, however I am hung up on a couple aspects of quantum ...
4
votes
2answers
73 views

Why do multi-bit hadamards expands to what they do?

I'm a Computer Scientist undergrad student studying for an exam in Quantum computing. In all of the algorithms I have been studying (Deutsch–Jozsa, Simons, Shors, Grovers) I constantly see multi-qubit ...
0
votes
1answer
86 views

Understanding how unitary operation changes state of system

While reading "Quantum Computation and Quantum Information" (by Nielsen and Chuang) I came across this line A little thought shows that if we apply $U_f$ to the state $\vert x \rangle (\dfrac{\...
2
votes
1answer
148 views

How to measure one of the qubits in a two-qubit register?

How do I measure the first qubit of an entangled vector, say \begin{pmatrix} 1 \\ -1 \\ 0 \\ 0 \\ \end{pmatrix} is what I get on the end of Deutsch's algorithm. If I get it right, I should now ...
5
votes
2answers
123 views

Probability estimate in classical Deutsch-Josza problem

I have already posed the question on Math SE but I hope that people from QC community can help. I am starting studying QC, but first, I want to understand the classical view of algorithms. So in the ...
8
votes
2answers
285 views

Why doesn't Deutsch-Jozsa Algorithm show that P ≠ BQP?

To my understanding, Deutsch-Jozsa algorithm solves a specific problem in constant time, using a fixed circuit depth, compared to a classical deterministic algorithm, which would require time ...
4
votes
2answers
165 views

Why is the Deutsch algorithm faster on a quantum computer?

I still don't understand what makes the Deutsch algorithm faster in a quantum computer. Why is it not same as in a classical computer? But this algorithm is just mathematics. All gates can be ...
4
votes
1answer
88 views

Implementing the one-bit Deutsch Oracle algorithm using phase

The standard method of implementing the one-bit Deutsch Oracle algorithm is to use two qbits, one as input & one as output (which allows you to write the non-reversible constant functions in a ...
2
votes
1answer
44 views

Analysis of the second Hadamard in the Detusch-Josza Algorithm

Consider the Deutsch-Josza, algorithm, which first initializes the state $|0 \rangle^{\otimes n} | 1 \rangle$, creates a superposition using the the Hadamard gate and the $U_f$ to get into the state: $...
4
votes
3answers
98 views

How to factor the output of a CNOT acting on the input $|-,+\rangle$

I am trying to implement the Deutsch oracle in classical computer, using direction from this talk. There is this slide where they show how the CNOT gate modify 2 Hadamard transformed Qubits: While ...
13
votes
5answers
3k views

How would I implement the quantum oracle in Deutsch's algorithm?

I am trying to simulate Deutsch's algorithm (elementary case of Deutsch-Josza algorithm), and I am not entirely sure how I would go about implementing the quantum oracle necessary for the algorithm to ...
3
votes
1answer
207 views

Deutsch-Jozsa on non-balanced oracles

I'm interested in deciding if an oracle is constant or not, but cannot guarantee that the non-constant oracles are balanced. The Deutsch-Jozsa seems like the obvious starting place, but handling the ...
8
votes
0answers
137 views

What are examples of non-oracular versions of famous oracular problems?

Most quantum algorithms proposed, including Deutsch-Jozsa, Simon's, Bernstein-Vazirani etc, involve querying an oracle. If I understand correctly, the speedups depend on the oracle being efficiently ...
1
vote
1answer
74 views

What does a zero state combined state vector for 2 qubits mean?

I was fiddling with the quantum circuit used for Deutsch's algorithm and I was led to a zero state as a result which is bizarre. I don't know how to explain this result. ***I'm using Nielsen and ...
3
votes
3answers
411 views

How can a CNOT gate change the control qbit (e.g. in the Deutsch Oracle problem)?

It is very confusing how the CNOT gate can change the properties of the controlled qubit (possibly because I am still stuck in the classical programming mindset): Many books have explained the ...
3
votes
1answer
258 views

Implementing Deutsch's problem on IBM Q composer

I tried to implement the Deutsch's problem on IBM Q but didn't get the results as expected. So here is the circuit for the Deutsch algorithm and this is my implementation on the composer: so let me ...
2
votes
1answer
86 views

How to understand Deutsch-Jozsa algorithm from an adiabatic perspective?

I'm trying to understand the Deutsch-Josza algorithm from an adiabatic perspective as presented in Adiabatic quantum computing A: Review of modern physics, vol 90, (2018) pp 015002-1 (arXiv version). ...
5
votes
1answer
1k views

Understanding the oracle in Deutsch's algorithm

I am reading John Watrous' notes from his course CPSC 519 on quantum computing. In a pre-discussion before presenting Deutsch's algorithm to determine whether a function is constant or not, the author ...
3
votes
1answer
109 views

What happens in Deutsch algorithm if I use equal input bits?

I am currently working on the algorithm of Deutsch. The algorithm defines two starting states, which are for $|x\rangle = |0\rangle$ and for $|y\rangle = |1\rangle$. So far, that's clear to me. But ...
3
votes
1answer
113 views

Deutsch-Jozsa algorithm as a generalization of Bernstein-Vazirani

It is known that both algorithms use the same gates: $H^{\oplus n}U_fH^{\oplus n}$. After the circuit, the qubits are in the state $\sum_y \left( \sum_x (-1)^{f(x)+xy} \right) |y\rangle $. In DJ's ...
1
vote
1answer
220 views

Correct way of expressing a measurement in a different computational basis

Sometimes we find that the result we want from a quantum algorithm is expressed in terms of a basis that is different from the usual computational basis, which I will call $$ B_C = \left\{ \lvert 0 \...
4
votes
1answer
463 views

Deutsch–Jozsa algorithm: why is $f$ constant?

I'm trying to understand how the Deutsch–Jozsa algorithm works with the following circuit: Circuit in Quirk Since we have the top 2 wires measuring $|0\rangle$ with 100% probability, it means $U_f$ ...
1
vote
1answer
210 views

What can be a mini research project based on Grover's algorithm or the Deutsch Jozsa algorithm?

I need to work out a research project on quantum computing as a part of my curriculum. I was wondering how to implement something theoretically with the basic knowledge I have. I have learned about ...
6
votes
2answers
726 views

How to prove that the query oracle is unitary?

The query oracle: $O_{x}|i\rangle|b\rangle = |i\rangle|b \oplus x_{i}\rangle$ used in algorithms like Deutsch Jozsa is unitary. How do I prove it is unitary?
7
votes
2answers
193 views

Balanced vs unbalanced superposition distinguisher

I've been looking at basic quantum algorithms such as the Deutsch-Jozsa algorithm that are able to characterize functions very well and I was wondering if similar approaches exist to characterize ...
7
votes
2answers
1k views

How is the Deutsch-Jozsa algorithm faster than classical for practical implementation?

There is something I really misunderstand about the Deutsch-Jozsa algorithm. To check if $f$ is balanced or constant, we use the following algorithm : Where $U_f$ gives $(x,y) \rightarrow (x, y \...
3
votes
0answers
79 views

Deutsch Algorithm on a Quantum Turing Machine

I understood how a Quantum Turing Machine works from this lecture. It would be great if someone could give an example of how this machine could be used to solve a real problem though, for example, ...