Skip to content

Instantly share code, notes, and snippets.

@WrathfulSpatula

WrathfulSpatula/tests.cpp

Last active April 29, 2019 13:19
Show Gist options
  • Save WrathfulSpatula/1b29b7ae6db8a6882f830ad4b79a68ab to your computer and use it in GitHub Desktop.
Save WrathfulSpatula/1b29b7ae6db8a6882f830ad4b79a68ab to your computer and use it in GitHub Desktop.
Download ZIP
Grover's search of an unstructured lookup table in Qrack
Raw
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
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment