circuit_to_formulacoloring_reduction

Code that reduces the problem of learning boolean circuits to the combinatorial optimization task of formula coloring.

https://github.com/n1kn4x/circuit_to_formulacoloring_reduction

Science Score: 54.0%

This score indicates how likely this project is to be science-related based on various indicators:

✓
CITATION.cff file
Found CITATION.cff file
✓
codemeta.json file
Found codemeta.json file
✓
.zenodo.json file
Found .zenodo.json file
○
DOI references
✓
Academic publication links
Links to: arxiv.org
○
Academic email domains
○
Institutional organization owner
○
JOSS paper metadata
○
Scientific vocabulary similarity
Low similarity (4.3%) to scientific vocabulary

Last synced: 10 months ago · JSON representation ·

Repository

Code that reduces the problem of learning boolean circuits to the combinatorial optimization task of formula coloring.

Basic Info

Host: GitHub
Owner: n1kn4x
Language: Python
Default Branch: main
Size: 27.3 KB

Statistics

Stars: 2
Watchers: 1
Forks: 0
Open Issues: 0
Releases: 1

Created over 3 years ago · Last pushed over 3 years ago

Metadata Files

Readme Citation

Boolean Circuit to Formula Coloring

This repository contains the code for constructing advantage-bearing formula coloring instances as described in the paper: "A super-polynomial quantum advantage for combinatorial optimization problems" (https://arxiv.org/abs/2212.08678)

Overview

The modules included in this repository are: - turing_machine.py: A module for defining Turing machines and their transition functions. - dfa.py: A module for defining Deterministic Finite Automata (DFA) and their transition functions. - boolean_circuit.py : A module for defining Boolean circuits.

A well as the reductions among them: - formula_to_tm.py: A module for reducing a Boolean Formula, as obtained from a Boolean Circuit, to a Turing machine. - tm_to_dfa.py: A module for reducing a Turing Machine to a DFA. - dfa_to_fc.py: A module for reducing a DFA to a formula coloring instance.

Usage

We provide some tests as an example on how to use the modules.

Owner

Name: Niklas Pirnay
Login: n1kn4x
Kind: user
Location: Berlin

Repositories: 1
Profile: https://github.com/n1kn4x

Citation (CITATION.cff)

# This CITATION.cff file was generated with cffinit.
# Visit https://bit.ly/cffinit to generate yours today!

cff-version: 1.2.0
title: Boolean circuit to formula coloring reduction
message: >-
  If you use this software, please cite it using the
  metadata from this file.
type: software
authors:
  - given-names: Niklas
    family-names: Pirnay
    email: n.pirnay@tu-berlin.de
    affiliation: TU Berlin
  - given-names: Vincent
    family-names: Ulitzsch
    affiliation: TU Belrin
  - given-names: Frederik
    family-names: Wilde
    affiliation: FU Berlin
  - given-names: Jens
    family-names: Eisert
    affiliation: FU Berlin
  - given-names: Jean-Pierre
    family-names: Seifert
    affiliation: TU Berlin
identifiers:
  - type: url
    value: >-
      https://github.com/n1kn4x/circuit_to_formulacoloring_reduction/releases/tag/v1.0.0
  - type: doi
    value: 10.5281/zenodo.7660988
repository-code: >-
  https://github.com/n1kn4x/circuit_to_formulacoloring_reduction
repository-artifact: >-
  https://github.com/n1kn4x/circuit_to_formulacoloring_reduction/releases/tag/v1.0.0
abstract: >-
  This repository contains the code for constructing
  advantage-bearing formula coloring instances as described
  in the paper: "A super-polynomial quantum advantage for
  combinatorial optimization problems"
  (https://arxiv.org/abs/2212.08678)
version: 1.0.0
date-released: '2023-02-21'

ecosyste.ms

Data

Tools

Indexes

Applications

Experiments

Open Source Science