Sep 24 2014
The effect of quantum wavefunction superposition is used to create software search parallelism in a newly issued US Patent 8,832,139 B2¹ to Panvia Future Technologies Inc., Palo Alto, California.
In software form, the effect of quantum wavefunction superposition means that multiple separate data combined inside a single representation can be searched in parallel. Panvia's innovation is a way to encode the components so that the matching data patterns are read directly, thus disambiguating the multiple different candidate potential data match hits in the superposition.
This new form of data search parallelism is created in conventional processors and can fully utilize the vector processing architectures of the latest generation Graphics Processor Unit (GPU) and Accelerated Processor Unit (APU) chips because quantum wavefunction superposition exists in software. As such, it does not require any exotic quantum hardware, unlike Lov Grover's Fast Quantum Mechanical Algorithms² that uses the theoretical hardware of quantum gates to create quantum entanglement.
Inherent parallelism of the new data searching algorithm allows it to scale to utilize the large number of Single Instruction Multiple Data (SIMD) vector processing compute units that are present in current GPU's and APU's. For example, using a medium range graphics card it is possible to process one billion searches per second for a 100 byte long 'keytag'.
Such giga-search per second performance is unprecedented.
Until now, a major problem has been that while existing data search algorithms have certain tricks to partition or reduce the search space, they always reduce at their core to the most common method of a basic serial search algorithm: where one record is bit-matched to each candidate in a long list until a match is found. Serial search has the characteristic that it has an unpredictable (or non-deterministic) search time since it depends on where the data is in the search order.
Multiple compute units may process separate serial searches, however serial comparison of one dimensional wide scalar variable does not fully utilize the typically sixty-four dimensional wide vector processor compute unit; there is a miss-match of traditional serial algorithm and modern vector processing hardware.
The short-comings of existing data search algorithms are most infamously exposed in the form of Distributed Denial of Service (DDoS) attacks that sadly remain the weapon of choice to bring down an internet website. These use distributed bot-nets to flood the Domain Name Server (DNS) with search requests, at a record rate of 300 Gigabits per second³.
A friendly flash mob could also cause the same devastating service impact because current web services get overloaded with search traffic. In either case this new US patent provides a search algorithm that is able to combine novel software parallelism with the hardware parallelism of hundreds of SIMD vector processors in a GPU to deliver a new era of giga-search per second performance that can cope with tomorrow's extreme cyber-challenges.