Simulates the algorithm from the paper 'A linear time quantum algorithm for 3SAT', which is actually exponential time.
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
LICENSE
README.md
classical_variant.py
simulate-walters.fs

README.md

This repository contains code for simulating Zachery B Walter's claimed Linear-time 3SAT algorithm with Microsoft's LIQUID, as well as code for simulating the classical variant of the algorithm.

Results

Based on the behavior of the simulation, and my analysis of the algorithm, I say it's actually exponential time.

Notice the way the right-side bits seem to be pulled to 100% in this recording:

Typical run

For some problem families, the effect gets exponentially stronger as the number of variables is increased.