Mixing
How to prevent future loops using a control qubit?
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
I am trying to construct a quantum multiplier using the method described here: https://arxiv.org/abs/quant-ph/0403048. However, it seems that the control qubit would only disable the following gates for one iteration. Afterward, the $|yrangle$ would still be in the fundamental, so would flip $D$ again and enable the next iteration of gates. How do I prevent all future iterations (essentially break out of the loop) using a control qubit?
quantum-gate
edited 2 hours ago
Blue
5,43811147
asked 4 hours ago
nikojpapa
975
add a comment |Â
up vote
3
down vote
favorite
I am trying to construct a quantum multiplier using the method described here: https://arxiv.org/abs/quant-ph/0403048. However, it seems that the control qubit would only disable the following gates for one iteration. Afterward, the $|yrangle$ would still be in the fundamental, so would flip $D$ again and enable the next iteration of gates. How do I prevent all future iterations (essentially break out of the loop) using a control qubit?
quantum-gate
edited 2 hours ago
Blue
5,43811147
asked 4 hours ago
nikojpapa
975
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
I am trying to construct a quantum multiplier using the method described here: https://arxiv.org/abs/quant-ph/0403048. However, it seems that the control qubit would only disable the following gates for one iteration. Afterward, the $|yrangle$ would still be in the fundamental, so would flip $D$ again and enable the next iteration of gates. How do I prevent all future iterations (essentially break out of the loop) using a control qubit?
quantum-gate
edited 2 hours ago
Blue
5,43811147
asked 4 hours ago
nikojpapa
975
I am trying to construct a quantum multiplier using the method described here: https://arxiv.org/abs/quant-ph/0403048. However, it seems that the control qubit would only disable the following gates for one iteration. Afterward, the $|yrangle$ would still be in the fundamental, so would flip $D$ again and enable the next iteration of gates. How do I prevent all future iterations (essentially break out of the loop) using a control qubit?
quantum-gate
quantum-gate
edited 2 hours ago
Blue
5,43811147
asked 4 hours ago
nikojpapa
975
edited 2 hours ago
Blue
5,43811147
asked 4 hours ago
nikojpapa
975
edited 2 hours ago
Blue
5,43811147
edited 2 hours ago
Blue
5,43811147
edited 2 hours ago
Blue
5,43811147
5,43811147
asked 4 hours ago
nikojpapa
975
asked 4 hours ago
nikojpapa
975
asked 4 hours ago
nikojpapa
975
975
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
You're correct, there is a bug in the algorithm described by the paper. D should be unconditionally decremented in each iteration, and the control (which I would instead call the accumulator... except it looks like it is actually intended to control it?) should be toggled if D=0. The author has made the mistake of conditioning the decrement on the accumulator, which will prevent $D=0$ from becoming $D=2^N-1$ in the relevant iteration and result in the accumulator re-toggling in the next iteration.
In any case, this is an extremely inefficient multiplier. It has cost $O(N 2^N)$ instead of the $O(N^2)$ you get from naive schoolbook multiplication. Just do this instead:
for index, qubit in enumerate(input1):
if qubit:
output += input2 << index
answered 2 hours ago
Craig Gidney
2,712117
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
You're correct, there is a bug in the algorithm described by the paper. D should be unconditionally decremented in each iteration, and the control (which I would instead call the accumulator... except it looks like it is actually intended to control it?) should be toggled if D=0. The author has made the mistake of conditioning the decrement on the accumulator, which will prevent $D=0$ from becoming $D=2^N-1$ in the relevant iteration and result in the accumulator re-toggling in the next iteration.
In any case, this is an extremely inefficient multiplier. It has cost $O(N 2^N)$ instead of the $O(N^2)$ you get from naive schoolbook multiplication. Just do this instead:
for index, qubit in enumerate(input1):
if qubit:
output += input2 << index
answered 2 hours ago
Craig Gidney
2,712117
add a comment |Â
up vote
2
down vote
You're correct, there is a bug in the algorithm described by the paper. D should be unconditionally decremented in each iteration, and the control (which I would instead call the accumulator... except it looks like it is actually intended to control it?) should be toggled if D=0. The author has made the mistake of conditioning the decrement on the accumulator, which will prevent $D=0$ from becoming $D=2^N-1$ in the relevant iteration and result in the accumulator re-toggling in the next iteration.
In any case, this is an extremely inefficient multiplier. It has cost $O(N 2^N)$ instead of the $O(N^2)$ you get from naive schoolbook multiplication. Just do this instead:
for index, qubit in enumerate(input1):
if qubit:
output += input2 << index
answered 2 hours ago
Craig Gidney
2,712117
add a comment |Â
up vote
2
down vote
up vote
2
down vote
You're correct, there is a bug in the algorithm described by the paper. D should be unconditionally decremented in each iteration, and the control (which I would instead call the accumulator... except it looks like it is actually intended to control it?) should be toggled if D=0. The author has made the mistake of conditioning the decrement on the accumulator, which will prevent $D=0$ from becoming $D=2^N-1$ in the relevant iteration and result in the accumulator re-toggling in the next iteration.
In any case, this is an extremely inefficient multiplier. It has cost $O(N 2^N)$ instead of the $O(N^2)$ you get from naive schoolbook multiplication. Just do this instead:
for index, qubit in enumerate(input1):
if qubit:
output += input2 << index
answered 2 hours ago
Craig Gidney
2,712117
You're correct, there is a bug in the algorithm described by the paper. D should be unconditionally decremented in each iteration, and the control (which I would instead call the accumulator... except it looks like it is actually intended to control it?) should be toggled if D=0. The author has made the mistake of conditioning the decrement on the accumulator, which will prevent $D=0$ from becoming $D=2^N-1$ in the relevant iteration and result in the accumulator re-toggling in the next iteration.
In any case, this is an extremely inefficient multiplier. It has cost $O(N 2^N)$ instead of the $O(N^2)$ you get from naive schoolbook multiplication. Just do this instead:
for index, qubit in enumerate(input1):
if qubit:
output += input2 << index
answered 2 hours ago
Craig Gidney
2,712117
edited 1 hour ago
answered 2 hours ago
Craig Gidney
2,712117
answered 2 hours ago
Craig Gidney
2,712117
answered 2 hours ago
Craig Gidney
2,712117
2,712117
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fquantumcomputing.stackexchange.com%2fquestions%2f4552%2fhow-to-prevent-future-loops-using-a-control-qubit%23new-answer', 'question_page');
);
Post as a guest
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
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
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
