Grover's search of an unstructured lookup table in Qrack

tests.cpp

//////////////////////////////////////////////////////////////////////////////////////
//
// (C) Daniel Strano and the Qrack contributors 2017-2019. All rights reserved.
//
// This example highlights the ways Qrack has to use Grover's search on an unstructured
// lookup table.
//
// Line #82 starts the 'textbook' variant of Grover's search. Line #119 starts the
// unstructured lookup table variant. Line #167 starts a (commented-out) working
// VM6502Q assembly variant of the unstructured lookup table variant.
//
// Licensed under the GNU Lesser General Public License V3.
// See LICENSE.md in the project root or https://www.gnu.org/licenses/lgpl-3.0.en.html
// for details.

#include <atomic>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>

#include "catch.hpp"
#include "qfactory.hpp"
#include "qneuron.hpp"

#include "tests.hpp"

using namespace Qrack;

#define ALIGN_SIZE 64
#define EPSILON 0.001
#define REQUIRE_FLOAT(A, B)                                                                                            \
    do {                                                                                                               \
        real1 __tmp_a = A;                                                                                             \
        real1 __tmp_b = B;                                                                                             \
        REQUIRE(__tmp_a < (__tmp_b + EPSILON));                                                                        \
        REQUIRE(__tmp_a > (__tmp_b - EPSILON));                                                                        \
    } while (0);

void print_bin(int bits, int d);
void log(QInterfacePtr p);

void print_bin(int bits, int d)
{
    int mask = 1 << bits;
    while (mask != 0) {
        printf("%d", !!(d & mask));
        mask >>= 1;
    }
}

void log(QInterfacePtr p) { std::cout << std::endl << std::showpoint << p << std::endl; }

unsigned char* cl_alloc(size_t ucharCount)
{
#if defined(__APPLE__)
    void* toRet;
    posix_memalign(&toRet, ALIGN_SIZE,
        ((sizeof(unsigned char) * ucharCount) < ALIGN_SIZE) ? ALIGN_SIZE : (sizeof(unsigned char) * ucharCount));
    return (unsigned char*)toRet;
#elif defined(_WIN32) && !defined(__CYGWIN__)
    return (unsigned char*)_aligned_malloc(
        ((sizeof(unsigned char) * ucharCount) < ALIGN_SIZE) ? ALIGN_SIZE : (sizeof(unsigned char) * ucharCount),
        ALIGN_SIZE);
#else
    return (unsigned char*)aligned_alloc(ALIGN_SIZE,
        ((sizeof(unsigned char) * ucharCount) < ALIGN_SIZE) ? ALIGN_SIZE : (sizeof(unsigned char) * ucharCount));
#endif
}

void cl_free(void* toFree)
{
    if (toFree) {
#if defined(_WIN32)
        _aligned_free(toFree);
#else
        free(toFree);
#endif
    }
}


TEST_CASE_METHOD(QInterfaceTestFixture, "test_grover")
{
    int i;

    // Grover's search inverts the function of a black box subroutine.
    // Our subroutine returns true only for an input of 100.

    const int TARGET_PROB = 100;

    // Our input to the subroutine "oracle" is 8 bits.
    qftReg->SetPermutation(0);
    qftReg->H(0, 8);

    // std::cout << "Iterations:" << std::endl;
    // Twelve iterations maximizes the probablity for 256 searched elements.
    for (i = 0; i < 12; i++) {
        // Our "oracle" is true for an input of "100" and false for all other inputs.
        qftReg->DEC(100, 0, 8);
        qftReg->ZeroPhaseFlip(0, 8);
        qftReg->INC(100, 0, 8);
        // This ends the "oracle."
        qftReg->H(0, 8);
        qftReg->ZeroPhaseFlip(0, 8);
        qftReg->H(0, 8);
        qftReg->PhaseFlip();
        // std::cout << "\t" << std::setw(2) << i << "> chance of match:" << qftReg->ProbAll(TARGET_PROB) << std::endl;
    }

    // std::cout << "Ind Result:     " << std::showbase << qftReg << std::endl;
    // std::cout << "Full Result:    " << qftReg << std::endl;
    // std::cout << "Per Bit Result: " << std::showpoint << qftReg << std::endl;

    qftReg->MReg(0, 8);

    REQUIRE_THAT(qftReg, HasProbability(0, 16, TARGET_PROB));
}

TEST_CASE_METHOD(QInterfaceTestFixture, "test_grover_lookup")
{
    int i;

    // Grover's search to find a value in a lookup table.
    // We search for 100. All values in lookup table are 1 except a single match.

    const bitLenInt indexLength = 8;
    const bitLenInt valueLength = 8;
    const bitLenInt carryIndex = indexLength + valueLength;
    const int TARGET_VALUE = 100;
    const int TARGET_KEY = 230;

    unsigned char* toLoad = cl_alloc(1 << indexLength);
    for (i = 0; i < (1 << indexLength); i++) {
        toLoad[i] = 1;
    }
    toLoad[TARGET_KEY] = TARGET_VALUE;

    // Our input to the subroutine "oracle" is 8 bits.
    qftReg->SetPermutation(0);
    qftReg->H(valueLength, indexLength);
    qftReg->IndexedLDA(valueLength, indexLength, 0, valueLength, toLoad);

    // Twelve iterations maximizes the probablity for 256 searched elements, for example.
    // For an arbitrary number of qubits, this gives the number of iterations for optimal probability.
    int optIter = M_PI / (4.0 * asin(1.0 / sqrt(1 << indexLength)));

    for (i = 0; i < optIter; i++) {
        // Our "oracle" is true for an input of "100" and false for all other inputs.
        qftReg->DEC(TARGET_VALUE, 0, valueLength);
        qftReg->ZeroPhaseFlip(0, valueLength);
        qftReg->INC(TARGET_VALUE, 0, valueLength);
        // This ends the "oracle."
        qftReg->X(carryIndex);
        qftReg->IndexedSBC(valueLength, indexLength, 0, valueLength, carryIndex, toLoad);
        qftReg->X(carryIndex);
        qftReg->H(valueLength, indexLength);
        qftReg->ZeroPhaseFlip(valueLength, indexLength);
        qftReg->H(valueLength, indexLength);
        // qftReg->PhaseFlip();
        qftReg->IndexedADC(valueLength, indexLength, 0, valueLength, carryIndex, toLoad);
    }

    REQUIRE_THAT(qftReg, HasProbability(0, indexLength + valueLength, TARGET_VALUE | (TARGET_KEY << valueLength)));
    cl_free(toLoad);
}

/**
 * VM6502Q assembly implementation:
; test program #10
; address: $0c00
; perform Grover's search on lookup table
; (match is at position 0xe6)
; store result in $0cff
;
; GINIT:	clq
;               ldx #$00
;		ldy #$0c
;               cln
;               clv
;               seq
;		hax
; 		lda $0f00,X
; GITER:	cln
;		seq
;		sez
;		cmp #$64
;		clz
;		pxc
;               sbc $0f00,X
;		pxc
;		sez
;               hax
;		qzz
;		clz
;		hax
;               adc $0f00,X
;		clq
; 		dey
;		bne GITER
;		cmp #$64
;		bne GINIT
;		stx $0bff
;		brk
;
ORG
$0c00
$1f $a2 $00 $a0 $0c $2f $b8 $3f $03 $bd $00 $0f $2f $3f $2b $c9
$64 $47 $14 $fd $00 $0f $14 $2b $03 $f7 $47 $03 $7d $00 $0f $1f
$88 $d0 $e9 $c9 $64 $d0 $d9 $8e $ff $0b $00

ORG
$0f00
$01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01
$01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01
$01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01
$01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01
$01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01
$01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01
$01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01
$01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01
$01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01
$01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01
$01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01
$01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01
$01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01
$01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01
$01 $01 $01 $01 $01 $01 $64 $01 $01 $01 $01 $01 $01 $01 $01 $01
$01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01 $01
*/