A toolkit to find the optimal quantum query complexity and query optimal quantum algorithm of arbitrary Boolean functions.
Project description
QuantumQueryOptimizer
By R. Teal Witter and Michael T. Czekanski
A toolkit to find the optimal quantum query complexity and query optimal quantum algorithm of arbitrary Boolean functions.
Consider a function f that maps from D to E where D is a subset of bitstrings of length n and E is the set of single bit outputs. In the query model, an algorithm looks at the bits of the input string x in D as few times as possible before correctly determing f(x). Given f, our program finds the optimal query complexity of a quantum algorithm that evaluates f and a span program (i.e. quantum algorithm) that meets this query complexity by solving a semidefinite program (SDP).
There are two ways to run our program.
First, explicitly specify the sets D and E.
Second, create one function that generates the set D for arbitrary bitstring length n
and another function that generates the set E from D according to f.
(Note: We provide example functions in boolean_functions.py
.)
Setup
Install via pip with pip install quantumqueryoptimizer
.
Example 1  Explicit Construction
We consider the Boolean function OR
on input bitstrings of length 2.
The output is '1'
if any bit is 1 and '0'
otherwise.
In this example, we explicitly define both D
and E
.
Then we call our function qqo.runSDP
after loading the
file quantum_query_optimizer.py
as qqo
.
import quantum_query_optimizer as qqo D = ['00', '01', '10', '11'] E = ['0', '1', '1', '1'] qqo.runSDP(D=D, E=E)
The corresponding output should look similar to:
n: 2
D: ['00', '01', '10', '11']
E: ['0', '1', '1', '1']
Optimal Query Complexity: 1.414
Number of Iterations: 73
Run Time: 0.067 seconds
Example 2  Function Construction
We again consider OR
on bitstrings of length 2.
In this example, though, we define functions to generate
all bitstrings of length n and evaluate the function OR
on D.
Then we pass our functions into qqo.runSDPForN
and specify
for which sizes of bitstring n
we want to solve the SDP.
import quantum_query_optimizer as qqo qqo.runSDPForN(getD=qqo.getDAll, getE=qqo.getEOR, n_end=2, n_start=2))
The corresponding output should look similar to:
n: 2
D: ['00', '01', '10', '11']
E: ['0', '1', '1', '1']
Optimal Query Complexity: 1.414
Number of Iterations: 73
Run Time: 0.058 seconds
(You can find both examples in examples.py
.)
Semidefinite Program Formulation
We use Ben Reichardt's formulation of the SDP for
optimal quantum query complexity (described in Theorem 6.2
)
and query optimal span program (Lemma 6.5
) in
Span programs and quantum query complexity:
The general adversary bound is nearly tight for every boolean function.
Alternating Direction Method
To solve Reichardt's SDP,
we use Zaiwen Wen, Donald Goldfarb, and Wotao Yin's
Algorithm 1
described in
Alternating direction augmented Lagrangian methods for semidefinite programming.
Project details
Release history Release notifications
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Filename, size  File type  Python version  Upload date  Hashes 

Filename, size quantum_query_optimizer0.1.2py3noneany.whl (12.9 kB)  File type Wheel  Python version py3  Upload date  Hashes View hashes 
Filename, size quantumqueryoptimizer0.1.2.tar.gz (10.7 kB)  File type Source  Python version None  Upload date  Hashes View hashes 
Hashes for quantum_query_optimizer0.1.2py3noneany.whl
Algorithm  Hash digest  

SHA256  97a8be40d35471a8bdd00781e9c6f09251f4c93b7014d48343a2babf31bba034 

MD5  2f593e875482953532247c83b45971d1 

BLAKE2256  4e603b95f80b6d100ad9bd7c5a3a95b5c5b0a6319ee3ae8e870c8636557afa9c 
Hashes for quantumqueryoptimizer0.1.2.tar.gz
Algorithm  Hash digest  

SHA256  e3ff9256bd9553ad4096ecb7f52cd13af7a4e6cc86f527c8eee62371faca1554 

MD5  8f254acddcb007a26b67a212e8688b08 

BLAKE2256  2252e150b32e4671ca5ccfd52a603e6993bbf1097c32ace20c2398401a73cb96 