Ttdfjt

Can you move between the attacks of a Twinned Booming Blade

Does this circuit have marginal voltage level problem?

Does the North Korea Kim Jong Un have an heir?

Is it possible that Curiosity measured its own methane or failed doing the spectrometry?

What could a Medieval society do with excess animal blood?

What is the right way to query an I2C device from an interrupt service routine?

Solving Equations with HeavisideTheta Functions

Has there ever been a cold war other than between the U.S. and the U.S.S.R.?

Why is the saxophone not common in classical repertoire?

What does the ash content of broken wheat really mean?

Who pays for increased security measures on flights to the US?

Should I cheat if the majority does it?

How can solar sailed ships be protected from space debris?

What caused the flashes in the video footage of Chernobyl?

Use real text instead of lipsum in moderncv quote alignment

List of Implementations for common OR problems

How to compute the number of centroids for K-means clustering algorithm given minimal distance?

Are the plates of a battery really charged?

Should I hide my travel history to the UK when I apply for an Australian visa?

What is a "tittering order"?

Is my background sufficient to start Quantum Computing

How can I know (without going to the station) if RATP is offering the Anti Pollution tickets?

SQL Server error 242 with ANSI datetime

Can I deep fry food in butter instead of vegetable oil?

Why is the second register needed to define bit flip quantum oracles in a way that distinguishes between complementary oracles?

Are there numerical differences between classical and quantum solutions of problems such as the Born-Jordan quantization?What is the difference between QAOA and Quantum Annealing?What is the relation between this CGI device and a quantum sorting algorithm?How to create a quantum algorithm that produces 2 n-bit sequences with equal number of 1-bits?Quantum Walk: Why the need of adding “tail” nodes to the root?What's an use case of the inner product between two q-bits in a quantum algorithm?Correspondence between the Topological model and Quantum Circuit modelIs there a way to reverse the amplitudes of a quantum system?Is the Bernstein-Vazirani algorithm dependent on the specific behavior of the oracle?Does an oracle use only the eigenstates of the quantum register?

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;

3

$begingroup$

If our input $x in 0, 1^n$ is given as a black box, we usually query an oracle as follows.

$$O_x|i, b rangle = (-1)^b x_i |i, b rangle$$

$i = 1, 2, cdots, n $ is the index of the input we are querying. $x_i$ is the value at that index. $b = 0, 1$ is an arbitrary Boolean value.

Why do we need the $|b rangle$ register? Why can't we have a query of the form

$$O_x|i rangle = (-1)^x_i |i rangle$$

This transformation is certainly unitary. Andrew Childs notes in his lecture that we can't distinguish between $x$ and $barx$ (bitwise complement of $x$) if we exclude the $|b rangle$ register. I don't see why this should be the case.

algorithm oracles

share|improve this question

edited Jun 26 at 17:17

Craig Gidney

5,18833 silver badges2323 bronze badges

asked Jun 24 at 18:14

BlackHat18BlackHat18

10666 bronze badges

$endgroup$

add a comment | 

3

$begingroup$

If our input $x in 0, 1^n$ is given as a black box, we usually query an oracle as follows.

$$O_x|i, b rangle = (-1)^b x_i |i, b rangle$$

$i = 1, 2, cdots, n $ is the index of the input we are querying. $x_i$ is the value at that index. $b = 0, 1$ is an arbitrary Boolean value.

Why do we need the $|b rangle$ register? Why can't we have a query of the form

$$O_x|i rangle = (-1)^x_i |i rangle$$

This transformation is certainly unitary. Andrew Childs notes in his lecture that we can't distinguish between $x$ and $barx$ (bitwise complement of $x$) if we exclude the $|b rangle$ register. I don't see why this should be the case.

algorithm oracles

share|improve this question

edited Jun 26 at 17:17

Craig Gidney

5,18833 silver badges2323 bronze badges

asked Jun 24 at 18:14

BlackHat18BlackHat18

10666 bronze badges

$endgroup$

add a comment | 

$begingroup$

If our input $x in 0, 1^n$ is given as a black box, we usually query an oracle as follows.

$$O_x|i, b rangle = (-1)^b x_i |i, b rangle$$

$i = 1, 2, cdots, n $ is the index of the input we are querying. $x_i$ is the value at that index. $b = 0, 1$ is an arbitrary Boolean value.

Why do we need the $|b rangle$ register? Why can't we have a query of the form

$$O_x|i rangle = (-1)^x_i |i rangle$$

This transformation is certainly unitary. Andrew Childs notes in his lecture that we can't distinguish between $x$ and $barx$ (bitwise complement of $x$) if we exclude the $|b rangle$ register. I don't see why this should be the case.

algorithm oracles

share|improve this question

edited Jun 26 at 17:17

Craig Gidney

5,18833 silver badges2323 bronze badges

asked Jun 24 at 18:14

BlackHat18BlackHat18

10666 bronze badges

$endgroup$

share|improve this question

edited Jun 26 at 17:17

Craig Gidney

5,18833 silver badges2323 bronze badges

asked Jun 24 at 18:14

BlackHat18BlackHat18

10666 bronze badges

share|improve this question

edited Jun 26 at 17:17

Craig Gidney

5,18833 silver badges2323 bronze badges

asked Jun 24 at 18:14

BlackHat18BlackHat18

10666 bronze badges

edited Jun 26 at 17:17

Craig Gidney

5,18833 silver badges2323 bronze badges

edited Jun 26 at 17:17

Craig Gidney

5,18833 silver badges2323 bronze badges

asked Jun 24 at 18:14

BlackHat18BlackHat18

10666 bronze badges

asked Jun 24 at 18:14

BlackHat18BlackHat18

10666 bronze badges

1 Answer
1

active

oldest

votes

4

$begingroup$

Consider the last part of your question:

Why can't we have a query of the form
$$O_x|i rangle = (-1)^x_i |i rangle$$
This transformation is certainly unitary. Andrew Childs notes [...] that we can't distinguish between $x$ and $barx$ (bitwise complement of $x$) if we exclude the $|b rangle$ register. I don't see why this should be the case.

Let $lvert psi rangle = sum_k u_k lvert k rangle$. Then:
$$beginalign* O_x lvert psi rangle & = sum_k (-1)^x_k u_k lvert k rangle \[2ex]
O_bar x lvert psi rangle & = sum_k (-1)^bar x_k u_k lvert k rangle \
& = sum_k (-1)^1 + x_k u_k lvert k rangle \
& = sum_k - (-1)^x_k u_k lvert k rangle \
&= - O_x lvert psi rangle.
endalign* $$
Because global phases (such as the factor difference between $O_bar x lvert psi rangle$ and $- O_x lvert psi rangle$) aren't detectable, it is impossible to distinguish between these two states. In fact, more properly speaking, they are the same state — and these two different vectors are just equivalent ways of representing it, as the differences they have do not correspond to any physical properties.

share|improve this answer

edited Jun 24 at 20:29

answered Jun 24 at 18:43

Niel de BeaudrapNiel de Beaudrap

6,88511 gold badge1212 silver badges3838 bronze badges

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "694"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fquantumcomputing.stackexchange.com%2fquestions%2f6575%2fwhy-is-the-second-register-needed-to-define-bit-flip-quantum-oracles-in-a-way-th%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

4

$begingroup$

Consider the last part of your question:

Why can't we have a query of the form
$$O_x|i rangle = (-1)^x_i |i rangle$$
This transformation is certainly unitary. Andrew Childs notes [...] that we can't distinguish between $x$ and $barx$ (bitwise complement of $x$) if we exclude the $|b rangle$ register. I don't see why this should be the case.

Let $lvert psi rangle = sum_k u_k lvert k rangle$. Then:
$$beginalign* O_x lvert psi rangle & = sum_k (-1)^x_k u_k lvert k rangle \[2ex]
O_bar x lvert psi rangle & = sum_k (-1)^bar x_k u_k lvert k rangle \
& = sum_k (-1)^1 + x_k u_k lvert k rangle \
& = sum_k - (-1)^x_k u_k lvert k rangle \
&= - O_x lvert psi rangle.
endalign* $$
Because global phases (such as the factor difference between $O_bar x lvert psi rangle$ and $- O_x lvert psi rangle$) aren't detectable, it is impossible to distinguish between these two states. In fact, more properly speaking, they are the same state — and these two different vectors are just equivalent ways of representing it, as the differences they have do not correspond to any physical properties.

share|improve this answer

edited Jun 24 at 20:29

answered Jun 24 at 18:43

Niel de BeaudrapNiel de Beaudrap

6,88511 gold badge1212 silver badges3838 bronze badges

$endgroup$

add a comment | 

4

$begingroup$

Consider the last part of your question:

Why can't we have a query of the form
$$O_x|i rangle = (-1)^x_i |i rangle$$
This transformation is certainly unitary. Andrew Childs notes [...] that we can't distinguish between $x$ and $barx$ (bitwise complement of $x$) if we exclude the $|b rangle$ register. I don't see why this should be the case.

Let $lvert psi rangle = sum_k u_k lvert k rangle$. Then:
$$beginalign* O_x lvert psi rangle & = sum_k (-1)^x_k u_k lvert k rangle \[2ex]
O_bar x lvert psi rangle & = sum_k (-1)^bar x_k u_k lvert k rangle \
& = sum_k (-1)^1 + x_k u_k lvert k rangle \
& = sum_k - (-1)^x_k u_k lvert k rangle \
&= - O_x lvert psi rangle.
endalign* $$
Because global phases (such as the factor difference between $O_bar x lvert psi rangle$ and $- O_x lvert psi rangle$) aren't detectable, it is impossible to distinguish between these two states. In fact, more properly speaking, they are the same state — and these two different vectors are just equivalent ways of representing it, as the differences they have do not correspond to any physical properties.

share|improve this answer

edited Jun 24 at 20:29

answered Jun 24 at 18:43

Niel de BeaudrapNiel de Beaudrap

6,88511 gold badge1212 silver badges3838 bronze badges

$endgroup$

add a comment | 

$begingroup$

Consider the last part of your question:

Why can't we have a query of the form
$$O_x|i rangle = (-1)^x_i |i rangle$$
This transformation is certainly unitary. Andrew Childs notes [...] that we can't distinguish between $x$ and $barx$ (bitwise complement of $x$) if we exclude the $|b rangle$ register. I don't see why this should be the case.

Let $lvert psi rangle = sum_k u_k lvert k rangle$. Then:
$$beginalign* O_x lvert psi rangle & = sum_k (-1)^x_k u_k lvert k rangle \[2ex]
O_bar x lvert psi rangle & = sum_k (-1)^bar x_k u_k lvert k rangle \
& = sum_k (-1)^1 + x_k u_k lvert k rangle \
& = sum_k - (-1)^x_k u_k lvert k rangle \
&= - O_x lvert psi rangle.
endalign* $$
Because global phases (such as the factor difference between $O_bar x lvert psi rangle$ and $- O_x lvert psi rangle$) aren't detectable, it is impossible to distinguish between these two states. In fact, more properly speaking, they are the same state — and these two different vectors are just equivalent ways of representing it, as the differences they have do not correspond to any physical properties.

share|improve this answer

edited Jun 24 at 20:29

answered Jun 24 at 18:43

Niel de BeaudrapNiel de Beaudrap

6,88511 gold badge1212 silver badges3838 bronze badges

$endgroup$

share|improve this answer

edited Jun 24 at 20:29

answered Jun 24 at 18:43

Niel de BeaudrapNiel de Beaudrap

6,88511 gold badge1212 silver badges3838 bronze badges

answered Jun 24 at 18:43

Niel de BeaudrapNiel de Beaudrap

6,88511 gold badge1212 silver badges3838 bronze badges

answered Jun 24 at 18:43

Niel de BeaudrapNiel de Beaudrap

6,88511 gold badge1212 silver badges3838 bronze badges