Skip to main content

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.)

Set-up

Install via pip with pip install quantum-query-optimizer.

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


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for quantum-query-optimizer, version 0.1.2
Filename, size File type Python version Upload date Hashes
Filename, size quantum_query_optimizer-0.1.2-py3-none-any.whl (12.9 kB) File type Wheel Python version py3 Upload date Hashes View hashes
Filename, size quantum-query-optimizer-0.1.2.tar.gz (10.7 kB) File type Source Python version None Upload date Hashes View hashes

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page