Space- and energy-efficientcomputing with DNA

Anne Condon, U. British Columbia

Motivation: Programming molecules• Compu ng technologies need not be limited to silicon!
• Nature provides an incredible, nanoscale, molecular toolkit• DNA molecules are par cularly nice to work with
• Poten al applica ons: nanocircuits, DNA storage, facile
disease diagnosis, smart drug delivery, and of course,
understanding our world

ti

ti

ti

ti

ti

ti

ti

ti

ti

ti

• Molecular programming also raises new theore cal ques ons,
pertaining to models of computa on, informa on encoding,error correc on, distributed compu ng, randomized
algorithms, and moreMotivation: Programming molecules

Motivation: Programming molecules
molecular program, as a Chemical Reaction Network (CRN)
X+X+Y→X+X+X
X+Y+Y→Y+Y+Y

Motivation: Programming molecules
molecular program, as a Chemical Reaction Network (CRN)
X+X+Y→X+X+X
X+Y+Y→Y+Y+Y

compile to
DNA

X

X
Y

analyze
the resultsYX

run the program fromsome initial configuration

Soloveichik et al., 2013; Chen et al., 2013

Motivation: Programming molecules
molecular program, as a Chemical Reaction Network (CRN)
X+X+Y→X+X+X
X+Y+Y→Y+Y+Y

DNA

X

X
Y

analyze
the resultsYX

run the program fromsome initial configuration

countcompile totime

Soloveichik et al., 2013; Chen et al., 2013

Motivation: Programming molecules

Motivation: Programming molecules

Motivation: Programming molecules

Motivation: Programming molecules
880 nmTikhomirov et al., 2017

Can computations be energy-efficient?

Can computations be energy-efficient?

“… capable of dissipating an arbitrarily small amount of energy perstep if operated sufficiently slowly” (Bennett, 1973).

Can computations be energy-efficient?
Landauer (1961): probably not, because
computations are typically logically irreversible (e.g.,
because they erase or overwrite memory); this
implies a lower bound on the entropy generated andenergy dissipated at every irreversible step.
Bennett (1973): maybe, because logically irreversible
computations can be simulated by logically reversible
ones, and it might be possible to simulate logicallyreversible computations by physically reversible ones

Landauer and Bennett, The Fundamental Physical Limits ofComputation Scientific American, 1985.

Can computations be energy-efficient?
Landauer (1961): probably not, because
computations are typically logically irreversible (e.g.,
because they erase or overwrite memory); this
implies a lower bound on the entropy generated andenergy dissipated at every irreversible step.
Bennett (1973): maybe, because logically irreversible
computations can be simulated by logically reversible
ones, and it might be possible to simulate logicallyreversible computations by physically reversible ones.

Landauer and Bennett, The Fundamental Physical Limits ofComputation Scientific American, 1985.

Can computations be energy-efficient?
logically
logically
Bennett
irreversible
reversible
computations
computations???

physicallyreversible
computations

Bennett showed how to simulate (irreversible) Turingmachines using logically reversible Turing machines.
Since Turing machines can be simulated by families of
Boolean circuits (one circuit per input length), which in turncan be simulated by stochastic CRNs, his ideas can just as
easily be illustrated using chemical reaction networks (CRNs).

Can computations be energy-efficient?
logically
logically
Bennett
irreversible
reversible
computations
computations???

physicallyreversible
computations

Bennett showed how to simulate (irreversible) Turingmachines using logically reversible Turing machines.
Turing machines can be simulated by families of Boolean
circuits, which in turn can be simulated by chemical reaction
networks (CRNs).

Example: a CRN for parity• input species: one copy each of X1, X2, …, Xn, Xi ∈ {0i,1i}• output:
N, if parity(X1, X2, …, Xn) = 0
Y, if parity(X1, X2, …, Xn) = 1

Example: a CRN for parity• input species: one copy each of X1, X2, …, Xn, Xi ∈ {0i,1i}• output:
N, if parity(X1, X2, …, Xn) = 0
Y, if parity(X1, X2, …, Xn) = 1• auxiliary input species: one copy of N
• reactions, 1 ≤ i ≤ n:
N + 0i → N
N + 1i → Y
Y + 0i → Y
Y + 1i → NExample: a CRN for parity• input species: one copy each of X1, X2, …, Xn, Xi ∈ {0i,1i}• output:
N, if parity(X1, X2, …, Xn) = 0
Y, if parity(X1, X2, …, Xn) = 1• auxiliary input species: one copy of N
• reactions, 1 ≤ i ≤ n:
N + 0i → N
N + 1i → Y
Y + 0i → Y
Y + 1i → N

This CRN is stochastic, andlogically irreversible: it’s notpossible in general to trace backto the initial input from a given
reachable configuration

Example: a logically reversible CRN for parity• input species: one copy each of X1, X2, …, Xn, Xi ∈ {0i,1i}
output:N, if parity(X1, X2, …, Xn) = 0
Y, if parity(X1, X2, …, Xn) = 1

Example: a logically reversible CRN for parity• input species: one copy each of X1, X2, …, Xn, Xi ∈ {0i,1i}• output:
N, if parity(X1, X2, …, Xn) = 0
Y, if parity(X1, X2, …, Xn) = 1• auxiliary input species: one copy of N and t0• reactions:Example: a logically reversible CRN for parity• input species: one copy each of X1, X2, …, Xn, Xi ∈ {0i,1i}• output:
N, if parity(X1, X2, …, Xn) = 0
Y, if parity(X1, X2, …, Xn) = 1• auxiliary input species: one copy of N and t0• reactions:
N + 01 + t0 → N + 01 + t1
N + 11 + t0 → Y + 11 + t1
N + 02 + t1 → N + 02 + t2
N + 12 + t1 → Y + 12 + t2
Y + 02 + t1 → Y + 02 + t2
Y + 12 + t1 → N + 12 + t2…

Example: a logically reversible CRN for parity• input species: one copy each of X1, X2, …, Xn, Xi ∈ {0i,1i}• output:
N, if parity(X1, X2, …, Xn) = 0
Y, if parity(X1, X2, …, Xn) = 1• auxiliary input species: one copy of N and t0• reactions:
N + 01 + t0 → N + 01 + t1
N + 11 + t0 → Y + 11 + t1
N + 02 + t1 → N + 02 + t2
N + 12 + t1 → Y + 12 + t2
Y + 02 + t1 → Y + 02 + t2
Y + 12 + t1 → N + 12 + t2…

This CRN is deterministic: atmost one reaction is applicable atany point, and logicallyreversible: there is only one way
to step backwards from areachable configuration.

Can computations be energy-efficient?
logically
logically
Bennett
irreversible
reversible
computations
computations???

physicallyreversible
computations

Can computations be energy-efficient?
logically
logically
Bennett
irreversible
reversible
computations
computations

t-step, deterministic
CRN with reactions:
Xj + X’j → Yj + Y’j
1 ≤ j≤ d???

physicallyreversible
computations

t-step deterministic, logically reversible
CRN:
auxiliary input species: ?i,1 ≤ i ≤ t, t0
ti-1 + ?i + Xj + X’j → ti + ji + Yj + Y’j
1 ≤ j ≤ d, 1 ≤ i ≤ tCan computations be energy-efficient?
logically
logically
Bennett
irreversible
reversible
computations
computations

physicallyreversible
computations

t-step deterministic, logically reversible
CRN:
auxiliary input species: ?i,1 ≤ j ≤ t, t0
ti-1 + ?i + Xj + X’j → ti + ji + Yj + Y’j
1 ≤ j ≤ d, 1 ≤ i ≤ tt-step, deterministic
CRN with reactions:
Xj + X’j → Yj + Y’j
1 ≤ j≤ dTime(t)???

⊆log-rev-Time(t)Can computations be energy-efficient?
logically
logically
Bennett
irreversible
reversible
computations
computations???

physicallyreversible
computations

Can computations be energy-efficient?
logically
logically
Bennett
irreversible
reversible
computations
computations???

physicallyreversible
computations“The existence of logically reversible automata suggests thatphysical computers might be made thermodynamically reversible,and hence capable of dissipating an arbitrarily small amount ofenergy per step if operated sufficiently slowly” (Bennett, 1973).

Can computations be energy-efficient?
logically
logically
Bennett
irreversible
reversible
computations
computations???

physicallyreversible
computations"The chemical realization of a logically reversible computation isa chain of reactions … a major reactant (analogous to DNA) …
encodes the logical state, and minor reactants react with the
major one to change the logical state … the minor reactants are
all present at definite concentrations, which may be manipulated
to drive the computation forward or backward." (Bennett, 1973).

Can computations be energy-efficient?
logically
logicallyphysically
Bennett
Qian et al.
irreversible
reversible
reversible
computations
computations
computations

Can computations be energy-efficient?
logically
logicallyphysically
Bennett
Qian et al.
irreversible
reversible
reversible
computations
computations
computations“Here we propose a chemical implementation of [computing
machines] using DNA strand displacement cascades as theunderlying chemical primitive. We capture the motivating feature ofBennett’s scheme: that physical reversibility corresponds to logicallyreversible computation, and arbitrarily little energy per computation
step is required.” (Qian et al., DNA 2011).

DSDs | DNA strand displacements

toehold complement

toehold

long domain complement

long domain

Soloveichik, Seelig, Winfree. “DNA as a universal
substrate for chemical kinetics”, PNAS 2010

DSDs | DNA strand displacements

DSDs | DNA strand displacements

DSDs | DNA strand displacements

DSDs | DNA strand displacements

reversible, and thus energy-efficientFrom CRNs to DSDs
A

+

B

⇌

C

From CRNs to DSDs

From CRNs to DSDs

three top strands
one bottom strand

From CRNs to DSDs

From CRNs to DSDs

From CRNs to DSDs

From CRNs to DSDs

From CRNs to DSDs

From CRNs to DSDs

From CRNs to DSDs

From CRNs to DSDs

From CRNs to DSDs

From CRNs to DSDs

From CRNs to DSDs
A

+

B

⇌

transformer moleculesCFrom CRNs to DSDs
A

+

B

⇌

C

transformer molecules"The chemical realization of a logically reversible computation is a chainof reactions … a major reactant (analogous to DNA) … encodes thelogical state, and minor reactants that react with the major one tochange the logical state … the minor reactants are all present at definite
concentrations, which may be manipulated to drive the computation
forward or backward." (Bennett, 1973).

From CRNs to DSDs
A

+

B

⇌

transformer moleculesClogically
logicallyphysically
Bennett
Qian et al.
irreversible
reversible
reversible
computations
computations
computations

Time(t)⊆log-rev-Time(t)⊆phys-revTime(poly(t))

Towards space- and energy-efficient computations

Towards space- and energy-efficient computations
a space-efficient countercounter execution

03 02 01
03 02 1103 12 01
03 12 11
13 02 01
13 02 11
13 12 0113 12 11

Towards space- and energy-efficient computations
a space-efficient countercounter execution
initial species:
0 3, 0 2, 0 1
reactions:
01 → 11
0 2 + 11 → 12 + 01
03 + 12 + 11 → 13 + 02 + 01

(1)
(2)
(3)

03 02 01
03 02 1103 12 01
03 12 11
13 02 01
13 02 11
13 12 0113 12 11

Towards space- and energy-efficient computations
a space-efficient countercounter execution
initial species:
0 3, 0 2, 0 1
reactions:
01 → 11
0 2 + 11 → 12 + 01
03 + 12 + 11 → 13 + 02 + 01

(1)
(2)
(3)

03 02 01
(1)
03 02 11(2)
03 12 01
03 12 11
13 02 01
13 02 11
13 12 0113 12 11

Towards space- and energy-efficient computations
a space-efficient countercounter execution
initial species:
0 3, 0 2, 0 1
reactions:
01 → 11
0 2 + 11 → 12 + 01
03 + 12 + 11 → 13 + 02 + 01

(1)
(2)
(3)

03 02 01
03 02 1103 12 01
03 12 11
13 02 01
13 02 11
13 12 0113 12 11

(1)
(2)
(1)
(3)
(1)
(2)
(1)

Towards space- and energy-efficient computations
a space-efficient countercounter execution
initial species:
0 3, 0 2, 0 1
reactions:
01 → 11
0 2 + 11 → 12 + 01
03 + 12 + 11 → 13 + 02 + 01

(1)
(2)
(3)

this binary counter CRN is• deterministic• logically reversible• space-efficient: n-bit counter uses
n species to count to 2n

03 02 01
03 02 1103 12 01
03 12 11
13 02 01
13 02 11
13 12 0113 12 11

(1)
(2)
(1)
(3)
(1)
(2)
(1)

Towards space- and energy-efficient computations
Space(s)???

log-rev-Space(s)???

phys-revSpace(poly(s))

Towards space- and energy-efficient computations
Space(s) Lange et al. log-rev-Space(s)???

phys-revSpace(poly(s))"[We] describe the simulation of an s(n) space-bounded deterministic
Turing machine by a reversible Turing machine operating in spaces(n). It thus answers a question posed by Bennett in 1989 and refutes
the conjecture made by Li and Vityani in 1996” (Lange et al., 1998).

Towards space- and energy-efficient computations
Space(s) Lange et al. log-rev-Space(s)???

phys-revSpace(poly(s))

Towards space- and energy-efficient computations
Space(s) Lange et al. log-rev-Space(s)???

phys-revSpace(poly(s))

Unfortunately, the compilation of deterministic, logically reversible
CRNs with s species into DSDs may result in an exponential
blow-up of the number of species, and thus the space (volume).
This is because of the transformer molecules needed by thecompilation.

Recall: transformer molecules
A

+

B

⇌

Tb

Tf

Tf +

A +

C

B

⇌

C + Tb

Accounting for transformers in the counter:counter execution

initial species:

03, 02, 01 (one copy each)reactions:
01 → 1102 + 11 → 12 + 01
0 3 + 12 + 11 → 13 + 02 + 01

(1)
(2)
(3)

03 02 01
03 02 1103 12 01
03 12 11
13 02 01
13 02 11
13 12 0113 12 11

(1)
(2)
(1)
(3)
(1)
(2)
(1)

Accounting for transformers in the counter:counter execution

initial species:

03, 02, 01 (one copy each)
Tf1 (min. four copies)

Tf2 (min. two copies)
Tf3 (min. one copy)
reactions:Tf1 +01 → 11+ Tr1 (1)Tf2 +02 + 11 → 12 + 01
+ Tr2 (2)
Tf3 + 03 + 12 + 11 → 13 + 02 + 01 + Tr3 (3)03 02 01
03 02 1103 12 01
03 12 11
13 02 01
13 02 11
13 12 0113 12 11

(1)
(2)
(1)
(3)
(1)
(2)
(1)

Towards space- and energy-efficient computations
Space(s) Lange et al. log-rev-Space(s)???

phys-revSpace(poly(s))

Towards space- and energy-efficient computations
Space(s) Lange et al. log-rev-Space(s)???

phys-revSpace(poly(s))

The Lange et al. construction suffers from the transformer
exponential blow-up problem of the traditional binary counter.
Is there a different way to construct a space-efficient, physicallyreversible counter?

Towards space- and energy-efficient computations
a Grey code countercounter execution

initial species:

03, 02, 01 (one copy each)
Tf1 (min. one copy)

Tf2 (min. one copy)
Tf3 (min. one copy)
reactions:Tf1 +01 ⇔ 11+ Tr1 (1)Tf2 +02 + 11 ⇔ 12 + 11
+ Tr2 (2)
Tf3 + 03 + 12 + 01 ⇔ 13 + 12 + 01 + Tr3 (3)03 02 01
03 02 1103 12 1103 12 0113 12 0113 12 11
13 02 11
13 02 01

(1-for)(2-for)(1-rev)(3-for)(1-for)(2-rev)(1-rev)Condon, Hu, Manuch, Thachuk., J. Royal Soc.

Towards space- and energy-efficient computations
a Grey code counter
accounting for transformer molecules:
initial species:

03, 02, 01 (one copy each)
Tf1 (min. one copy)

Tf2 (min. one copy)
Tf3 (min. one copy)
reactions:Tf1 +01 ⇔ 11+ Tr1 (1)Tf2 +02 + 11 ⇔ 12 + 11
+ Tr2 (2)
Tf3 + 03 + 12 + 01 ⇔ 13 + 12 + 01 + Tr3 (3)counter execution

03 02 01
03 02 1103 12 1103 12 0113 12 0113 12 11
13 02 11
13 02 01

(1-for)(2-for)(1-rev)(3-for)(1-for)(2-rev)(1-rev)Condon, Hu, Manuch, Thachuk., J. Royal Soc.

Towards space- and energy-efficient computations
a Grey code counter
accounting for transformer molecules:
initial species:

03, 02, 01 (one copy each)
Tf1 (min. one copy)

Tf2 (min. one copy)
Tf3 (min. one copy)
reactions:Tf1 +01 ⇔ 11+ Tr1 (1)Tf2 +02 + 11 ⇔ 12 + 11
+ Tr2 (2)
Tf3 + 03 + 12 + 01 ⇔ 13 + 12 + 01 + Tr3 (3)counter execution

03 02 01
03 02 1103 12 1103 12 0113 12 0113 12 11
13 02 11
13 02 01

(1-for)(2-for)(1-rev)(3-for)(1-for)(2-rev)(1-rev)Condon, Hu, Manuch, Thachuk., J. Royal Soc.

Towards space- and energy-efficient computations
a Grey code counter
accounting for transformer molecules:
initial species:

03, 02, 01 (one copy each)
Tf1 (min. one copy)

Tf2 (min. one copy)
Tf3 (min. one copy)
reactions:Tf1 +01 ⇔ 11+ Tr1 (1)Tf2 +02 + 11 ⇔ 12 + 11
+ Tr2 (2)
Tf3 + 03 + 12 + 01 ⇔ 13 + 12 + 01 + Tr3 (3)counter execution

03 02 01
03 02 1103 12 1103 12 0113 12 0113 12 11
13 02 11
13 02 01

(1-for)(2-for)(1-rev)(3-for)(1-for)(2-rev)(1-rev)Condon, Hu, Manuch, Thachuk., J. Royal Soc.

Towards space- and energy-efficient computations
a Grey code counter
accounting for transformer molecules:transformer molecules are recycled!
initial species:

03, 02, 01 (one copy each)
Tf1 (min. one copy)

Tf2 (min. one copy)
Tf3 (min. one copy)
reactions:Tf1 +01 ⇔ 11+ Tr1 (1)Tf2 +02 + 11 ⇔ 12 + 11
+ Tr2 (2)
Tf3 + 03 + 12 + 01 ⇔ 13 + 12 + 01 + Tr3 (3)counter execution

03 02 01
03 02 1103 12 1103 12 0113 12 0113 12 11
13 02 11
13 02 01

(1-for)(2-for)(1-rev)(3-for)(1-for)(2-rev)(1-rev)Condon, Hu, Manuch, Thachuk., J. Royal Soc.

Towards space- and energy-efficient computations

Towards space- and energy-efficient computations
Space(s) Lange et al. log-rev-Space(s)???

phys-revSpace(poly(s))

The Lange et al. construction suffers from the transformer
exponential blow-up of the traditional binary counter.

Lange, McKenzie, and Tapp, JCSS 2000

Towards space- and energy-efficient computations
Space(s) Lange et al. log-rev-Space(s)???

phys-revSpace(poly(s))

The Lange et al. construction suffers from the transformer
exponential blow-up of the traditional binary counter.

Space(s)Thachuk,
Condonlog-revSpace(poly(s))

Thachuk,
Condonphys-revSpace(poly(s))

Fortunately, building on the grey code counter, a space-efficientcompilation of a space-bounded CRN to a physically-reversible
DSD is possible.
Thachuk, Condon, DNA18, 2012

Towards space- and energy-efficient computations
Space(s)Thachuk,
Condonlog-revSpace(poly(s))

Thachuk,
Condonphys-revSpace(poly(s))

Key ideas:• A CRN with O(n) species can check the truth of a Quantified
SAT instance with n variables• Concentrations of “minor reactants” (transformers) are thesame, so forward and reverse reactions are equally likely• It’s easy to adapt the construction (by doubling the computation
length) so that once the output bit is produced, it’s present halfof the timeThachuk, Condon, DNA18, 2012

Towards space- and energy-efficient computations
Space(s)Thachuk,
Condonlog-revSpace(poly(s))

Thachuk,
Condonphys-revSpace(poly(s))

Key ideas:• A CRN with O(n) species can check the truth of a Quantified
SAT instance with n variables• Concentrations of “minor reactants” (transformers) are thesame, so forward and reverse reactions are equally likely• It’s easy to adapt the construction (by doubling the computation
length) so that once the output bit is produced, it’s present halfof the timeThachuk, Condon, DNA18, 2012

Towards space- and energy-efficient computations
Space(s)Thachuk,
Condonlog-revSpace(poly(s))

Thachuk,
Condonphys-revSpace(poly(s))

Key ideas:• A CRN with O(n) species can check the truth of a Quantified
SAT instance with n variables• Concentrations of “minor reactants” (transformers) are thesame, so forward and reverse reactions are equally likely• It’s easy to adapt the construction (by doubling the computation
length) so that once the output bit is produced, it’s present halfof the timeThachuk, Condon, DNA18, 2012

Towards space- and energy-efficient computations
Space(s)Thachuk,
Condonlog-revSpace(poly(s))

Thachuk,
Condonphys-revSpace(poly(s))

Key ideas:• A CRN with O(n) species can check the truth of a Quantified
SAT instance with n variables• Concentrations of “minor reactants” (transformers) are thesame, so forward and reverse reactions are equally likely• It’s easy to adapt the construction (by doubling the computation
length) so that once the output bit is produced, it’s present halfof the timeThachuk, Condon, DNA18, 2012

Towards space- and energy-efficient computations
Space(s)Thachuk,
Condonlog-revSpace(poly(s))

Thachuk,
Condonphys-revSpace(poly(s))

Key ideas:• A CRN with O(n) species can check the truth of a Quantified
SAT instance with n variables• Concentrations of “minor reactants” (transformers) are thesame, so forward and reverse reactions are equally likely• It’s easy to adapt the construction (by doubling the computation
length) so that once the output bit is produced, it’s present halfof the timeThachuk, Condon, DNA18, 2012

Summary

Logically and physically reversible simulations of irreversible
computations are necessary for energy-efficient computations.
Using reactions in both directions to advance a computation in a
logically reversible way seems useful in facilitating physicallyreversible, space-efficient computations.

Open questions

Open questions
Space(s)Lange et al. log-rev-

Space(s)???

phys-revSpace(s)Is there a compiler from CRNs to DSDs, or to an alternative
physically reversible DNA computing model, that does not sufferfrom the exponential blow-up problem?

Open questions
Space(s) Thachuk,
Condonlog-revSpace(s2 log s)Thachuk,
Condonphys-revSpace(s2 log s)

Is it possible to avoid the polynomial increase in space here? Orat least remove the log s factor?

Open questions
Space(s) Thachuk,
Condonlog-revSpace(s2 log s)Thachuk,
Condonphys-revSpace(s2 log s)

Open questions
Space(s) Thachuk,
Condonlog-revSpace(s2 log s)Thachuk,
Condonphys-revSpace(poly(s))

A logically reversible computation is k-balanced if, within every
computation pre x, the number of times that the transition is
executed in the forwards direction differs from the number oftimes that the transition is executed in the reverse direction byat most k.

fi

If BalancedSPACE(s(n)) is the class of languages recognizableby O(1)-balanced, logically reversible Turing machines, can weshow that DSPACE(s(n)) = BalancedSPACE(s(n))?

Open questions
initial species:

03, 02, 01 (one copy each)
Tf1 (min. four copies)

Tf2 (min. two copies)
Tf3 (min. one copy)
reactions:Tf1 +01 → 11+ Tr1 (1)Tf2 +02 + 11 → 12 + 01
+ Tr2 (2)
Tf3 + 03 + 12 + 11 → 13 + 02 + 01 + Tr3 (3)Can forward and backwards transformers be interconverted?

Thank you!

“Energy permits things to exist and to act, but
programming permits things to be purposeful”- Ware