Last modified: 2023-07-07
Abstract
Boolean networks (BNs) are simple mathematical dynamic models describing gene regulatory interactions [1,2]. Network components are represented as expressed (1) or not expressed (0). Logical rules combining network components via the operators AND, OR, and NOT describe the system’s interactions. Repeated evaluation of these update rules generates complex dynamics, leading to stable states called attractors. Knowledge of attractors is of interest in the biological context as these states correspond to cellular phenotypes [3].
The dynamic state space of BNs grows exponentially with the number of components, limiting analyses of larger systems. Motivated by the limits of traditional processors and the search for alternative hardware, we make use of gate-based, universal quantum computers which can perform calculations in an exponentially growing state space using a linearly increasing number of qubits. Thus, quantum hardware can capture the complexity of the model’s dynamics.
In our previous work, we implemented BNs on quantum computers, highlighting how quantum algorithms can be used to obtain information about network dynamics [4].
Building on this, we now propose a quantum circuit performing a search through the entire state space based on Grover’s algorithm [5,6], aiming to identify the entire set of attractors.
Grover’s algorithm works by iteratively amplifying the weight associated with a specified subset of states, followed by a probabilistic readout of a single possible solution. In contrast, we invert the roles of solution and non-solution states, resulting in a suppression of previously identified attractors. After every readout leading to the detection of a new attractor, this state is then added as a constraint to the quantum circuit in all further runs. In this manner, the search space can be restricted to assign increased weight to states which leads to novel attractors without requiring previous knowledge of the distribution or number of attractors in the system.
This also allows for the detection of small attractors, which may be difficult to find using a classical random sampling of states. Such attractors may nevertheless be biologically interesting, e.g. in the early detection of rare but drug-resistant phenotypes in a network modeling cancer.
We demonstrate this algorithm on a small biologically motivated Boolean network with attractors of different sizes. We analyze its performance when accounting for the noise present in real quantum processors and quantify the improvement that can be gained from error mitigation techniques. Furthermore, we are investigating the possibility of implementing a constraint-based attractor search using quantum annealers rather than gate-based processors due to the increased number of qubits available on such devices.
@font-face {font-family:"Cambria Math"; panose-1:2 4 5 3 5 4 6 3 2 4; mso-font-charset:0; mso-generic-font-family:roman; mso-font-pitch:variable; mso-font-signature:-536870145 1107305727 0 0 415 0;}@font-face {font-family:"Arial Unicode MS"; panose-1:2 11 6 4 2 2 2 2 2 4; mso-font-charset:128; mso-generic-font-family:swiss; mso-font-pitch:variable; mso-font-signature:-134238209 -371195905 63 0 4129279 0;}@font-face {font-family:"Helvetica Neue"; panose-1:2 0 5 3 0 0 0 2 0 4; mso-font-charset:0; mso-generic-font-family:auto; mso-font-pitch:variable; mso-font-signature:-452984065 1342208475 16 0 1 0;}@font-face {font-family:"\@Arial Unicode MS"; panose-1:2 11 6 4 2 2 2 2 2 4; mso-font-charset:128; mso-generic-font-family:swiss; mso-font-pitch:variable; mso-font-signature:-134238209 -371195905 63 0 4129279 0;}p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-unhide:no; mso-style-qformat:yes; mso-style-parent:""; margin:0cm; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Times New Roman",serif; mso-fareast-font-family:"Arial Unicode MS"; border:none; mso-ansi-language:EN-US; mso-fareast-language:EN-US;}p.Default, li.Default, div.Default {mso-style-name:Default; mso-style-unhide:no; mso-style-parent:""; margin-top:8.0pt; margin-right:0cm; margin-bottom:0cm; margin-left:0cm; line-height:120%; mso-pagination:widow-orphan; font-size:12.0pt; font-family:"Helvetica Neue"; mso-fareast-font-family:"Arial Unicode MS"; mso-bidi-font-family:"Arial Unicode MS"; color:black; border:none; mso-style-textoutline-type:none; mso-style-textoutline-outlinestyle-dpiwidth:0pt; mso-style-textoutline-outlinestyle-linecap:flat; mso-style-textoutline-outlinestyle-join:bevel; mso-style-textoutline-outlinestyle-pctmiterlimit:0%; mso-style-textoutline-outlinestyle-dash:solid; mso-style-textoutline-outlinestyle-align:center; mso-style-textoutline-outlinestyle-compound:simple; mso-ansi-language:DE;}.MsoChpDefault {mso-style-type:export-only; mso-default-props:yes; font-size:10.0pt; mso-ansi-font-size:10.0pt; mso-bidi-font-size:10.0pt; mso-fareast-font-family:"Arial Unicode MS"; border:none; mso-font-kerning:0pt; mso-ligatures:none;}.MsoPapDefault {mso-style-type:export-only;}div.WordSection1 {page:WordSection1;}