Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

LookAheadDKRSAddLE does not handle carry-in properly #2101

Open
bdg221 opened this issue Jan 9, 2025 · 0 comments
Open

LookAheadDKRSAddLE does not handle carry-in properly #2101

bdg221 opened this issue Jan 9, 2025 · 0 comments
Labels
bug Something isn't working needs triage

Comments

@bdg221
Copy link

bdg221 commented Jan 9, 2025

Describe the bug

The function description and API doc claim to accept a carry-in qubit in the zs[0] location, but it does not handle the carry-in properly all of the time.

/// # Description
/// Computes zs := xs + ys + zs[0] modulo 2ⁿ, where xs, ys, and zs are
/// little-endian registers, Length(xs) = Length(ys) ≤ Length(zs) = n,
/// assuming zs is 0-initialized, except for maybe zs[0], which can be
/// in |0> or |1> state and can be used as carry-in.
/// NOTE: `zs[Length(xs)]` can be used as carry-out, if `zs` is longer than `xs`.
/// This operation uses the carry-lookahead algorithm.

To Reproduce
The following code tests zs := xs + ys +zs[0] with both LookAheadDKRSAddLE and RippleCarryCGAddLE. In an example of a failing scenario:
xs = 1 = "100"
ys = 4 = "001"
zs = 1 = "100" where z[0] =1 for the carry in

Steps to reproduce the behavior:

    let n = 3;

    // x = 1
    use x = Qubit[n];
    ApplyPauliFromBitString(PauliX, true, Std.Convert.IntAsBoolArray(1, n), x);
    // y = 4
    use y = Qubit[n];
    ApplyPauliFromBitString(PauliX, true, Std.Convert.IntAsBoolArray(4, n), y);

    // z = 1 so that z[0] = 1 for carry in
    use dkrs_z = Qubit[n];
    ApplyPauliFromBitString(PauliX, true, Std.Convert.IntAsBoolArray(1, n), dkrs_z);

    // z= 1 so that z[0] = 1 for carry in
    use cg_z = Qubit[n];
    ApplyPauliFromBitString(PauliX, true, Std.Convert.IntAsBoolArray(1, n), cg_z);

    Std.Arithmetic.LookAheadDKRSAddLE(x, y, dkrs_z);
    Std.Arithmetic.RippleCarryCGAddLE(x, y, cg_z);

    let x_val = MeasureInteger(x);
    let y_val = MeasureInteger(y);
    let dkrs_ans = MeasureInteger(dkrs_z);
    let cg_ans = MeasureInteger(cg_z);
    Message($"x={x_val} y={y_val} carry_in=1 DKRS answer={dkrs_ans} CG answer={cg_ans}");

This results in:
x=1 y=4 carry_in=1 DKRS answer=4 CG answer=6

Note, if x=1, y=1, and carry_in=1 both DKRS and CG adders return the correct answer 3.

@bdg221 bdg221 added bug Something isn't working needs triage labels Jan 9, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working needs triage
Projects
None yet
Development

No branches or pull requests

1 participant