🐛 QuickExact returns duplicate charge configurations

[wlambooy]

fiction version

fiction main -- latest to date (62a132f)

OS

Ubuntu 22.04.2 LTS | Linux 5.15.133.1-microsoft-standard-WSL2 x86_64 GNU/Linux

Python version

3.11.2

C++ compiler

Ubuntu clang version 14.0.0-1ubuntu1.1

Additional environment information

No response

Description

As the title states, I found as 20 DB layout (unfortunately not a smaller one thus far) for which QuickExact returns 4 physically valid charge distributions, yet the test below shows evidence that there are actually 2 unique physically valid charge distributions.

Expected behavior

An SiDB simulator should not return duplicate results, this could indicate some hidden inefficiency too.

How to Reproduce

#include <fiction/algorithms/simulation/sidb/quickexact.hpp>
#include <fiction/algorithms/simulation/sidb/sidb_simulation_parameters.hpp>
#include <fiction/algorithms/simulation/sidb/sidb_simulation_result.hpp>
#include <fiction/technology/charge_distribution_surface.hpp>
#include <fiction/technology/sidb_charge_state.hpp>
#include <fiction/types.hpp>

#include <cstdint>

TEST_CASE("QuickExact duplicate charge configurations", "[quickexact]")
{
    using sidb_lyt = sidb_cell_clk_lyt_siqad;
    sidb_lyt lyt{};

    lyt.assign_cell_type({3, 0, 0}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({4, 0, 0}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({13, 0, 1}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({5, 1, 1}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({22, 3, 0}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({11, 5, 1}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({2, 6, 1}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({4, 6, 1}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({23, 7, 1}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({16, 8, 0}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({8, 8, 1}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({15, 9, 0}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({1, 10, 1}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({12, 10, 1}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({14, 10, 1}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({9, 11, 0}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({24, 11, 0}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({10, 11, 1}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({13, 12, 0}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({24, 12, 0}, sidb_lyt::cell_type::NORMAL);


    // not needed, but I'm giving all default parameters explicitly for the sake of the test
    const sidb_simulation_parameters params{3, -0.32, 5.6, 5.0, 3.84, 7.68, 2.25};

    const sidb_simulation_result<sidb_lyt>& qe_res = quickexact(lyt, quickexact_params<sidb_lyt>{params, quickexact_params<sidb_lyt>::automatic_base_number_detection::ON, {}, 0});

    // QuickExact returns 4 physically valid charge layout
    REQUIRE(qe_res.charge_distributions.size() == 4);

    // This loop asserts that the first two are equal
    for (uint64_t i = 0; i < 2; ++i)
    {
        CHECK(qe_res.charge_distributions[i].get_charge_state({3, 0, 0}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({4, 0, 0}) == sidb_charge_state::POSITIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({13, 0, 1}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({5, 1, 1}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({22, 3, 0}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({11, 5, 1}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({2, 6, 1}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({4, 6, 1}) == sidb_charge_state::NEUTRAL);
        CHECK(qe_res.charge_distributions[i].get_charge_state({23, 7, 1}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({16, 8, 0}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({8, 8, 1}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({15, 9, 0}) == sidb_charge_state::NEUTRAL);
        CHECK(qe_res.charge_distributions[i].get_charge_state({1, 10, 1}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({12, 10, 1}) == sidb_charge_state::NEUTRAL);
        CHECK(qe_res.charge_distributions[i].get_charge_state({14, 10, 1}) == sidb_charge_state::NEUTRAL);
        CHECK(qe_res.charge_distributions[i].get_charge_state({9, 11, 0}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({24, 11, 0}) == sidb_charge_state::NEUTRAL);
        CHECK(qe_res.charge_distributions[i].get_charge_state({10, 11, 1}) == sidb_charge_state::POSITIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({13, 12, 0}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({24, 12, 0}) == sidb_charge_state::NEGATIVE);
    }

    // This loop asserts that the last two are equal
    for (uint64_t i = 2; i < 4; ++i)
    {
        CHECK(qe_res.charge_distributions[i].get_charge_state({3, 0, 0}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({4, 0, 0}) == sidb_charge_state::POSITIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({13, 0, 1}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({5, 1, 1}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({22, 3, 0}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({11, 5, 1}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({2, 6, 1}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({4, 6, 1}) == sidb_charge_state::NEUTRAL);
        CHECK(qe_res.charge_distributions[i].get_charge_state({23, 7, 1}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({16, 8, 0}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({8, 8, 1}) == sidb_charge_state::NEUTRAL);
        CHECK(qe_res.charge_distributions[i].get_charge_state({15, 9, 0}) == sidb_charge_state::NEUTRAL);
        CHECK(qe_res.charge_distributions[i].get_charge_state({1, 10, 1}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({12, 10, 1}) == sidb_charge_state::NEUTRAL);
        CHECK(qe_res.charge_distributions[i].get_charge_state({14, 10, 1}) == sidb_charge_state::NEUTRAL);
        CHECK(qe_res.charge_distributions[i].get_charge_state({9, 11, 0}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({24, 11, 0}) == sidb_charge_state::NEUTRAL);
        CHECK(qe_res.charge_distributions[i].get_charge_state({10, 11, 1}) == sidb_charge_state::NEUTRAL);
        CHECK(qe_res.charge_distributions[i].get_charge_state({13, 12, 0}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({24, 12, 0}) == sidb_charge_state::NEGATIVE);
    }
}

[wlambooy]

Much to your benefit, I found a 5 DB example with the same issue :)

TEST_CASE("QuickExact duplicate charge configurations", "[quickexact]")
{
    using sidb_lyt = sidb_cell_clk_lyt_siqad;
    sidb_lyt lyt{};

    lyt.assign_cell_type({2, 2, 1}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({2, 3, 0}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({7, 3, 1}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({7, 4, 0}, sidb_lyt::cell_type::NORMAL);
    lyt.assign_cell_type({8, 4, 1}, sidb_lyt::cell_type::NORMAL);


    const sidb_simulation_result<sidb_lyt>& qe_res = quickexact(lyt);

    // QuickExact returns 3 physically valid charge distributions in total
    REQUIRE(qe_res.charge_distributions.size() == 3);
    
    // This loop asserts that the first two are equal
    for (uint64_t i = 0; i < 2; ++i)
    {
        CHECK(qe_res.charge_distributions[i].get_charge_state({2, 2, 1}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({2, 3, 0}) == sidb_charge_state::NEUTRAL);
        CHECK(qe_res.charge_distributions[i].get_charge_state({7, 3, 1}) == sidb_charge_state::NEGATIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({7, 4, 0}) == sidb_charge_state::POSITIVE);
        CHECK(qe_res.charge_distributions[i].get_charge_state({8, 4, 1}) == sidb_charge_state::NEGATIVE);
    }
}