# DeepTPI: Test Point Insertion with Deep Reinforcement Learning

Zhengyuan Shi1§, Min Li1§, Sadaf Khan1, Liuzheng Wang2, Naixing Wang2, Yu
Huang2 and Qiang Xu1  1Department of Computer Science and Engineering, The
Chinese University of Hong Kong, Shatin, Hong Kong S.A.R.
{zyshi21, mli, skhan<EMAIL_ADDRESS>2HiSilicon Technologies Co., Ltd.,
China

###### Abstract

Test point insertion (TPI) is a widely used technique for testability
enhancement, especially for logic built-in self-test (LBIST) due to its
relatively low fault coverage. In this paper, we propose a novel TPI approach
based on deep reinforcement learning (DRL), named _DeepTPI_. Unlike previous
learning-based solutions that formulate the TPI task as a supervised-learning
problem, we train a novel DRL agent, instantiated as the combination of a
graph neural network (GNN) and a Deep Q-Learning network (DQN), to maximize
the test coverage improvement. Specifically, we model circuits as directed
graphs and design a graph-based value network to estimate the action values
for inserting different test points. The policy of the DRL agent is defined as
selecting the action with the maximum value. Moreover, we apply the general
node embeddings from a pre-trained model to enhance node features, and propose
a dedicated testability-aware attention mechanism for the value network.
Experimental results on circuits with various scales show that DeepTPI
significantly improves test coverage compared to the commercial DFT tool. The
code of this work is available at https://github.com/cure-lab/DeepTPI.

§§footnotetext: Both authors contributed equally to this research.

##  I Introduction

Logic built-in-self-test (LBIST) [1] is a commonly used technique for in-field
tests, especially for many safety-critical scenarios [2], such as self-driving
cars, healthcare systems, and aircraft operating systems that have strict
reliability requirements. LBIST uses a pseudo-random pattern generator to
simulate the circuit behavior and verifies the corresponding responses. While
LBIST demands low hardware and computational overhead, it fails to detect the
random pattern resistant (RPR) faults [1]. The RPR fault commonly occurs in
complex modern circuits, where the gate has many fan-in wires. In most cases,
there is only one valid input assignment out of the quadratic fan-in number of
total random combinations. Therefore, the existence of the RPR faults results
in the insufficient test coverage under pseudo-random test.

To improve the low test coverage of LBIST caused by RPR faults, test point
insertion (TPI) [3] has been studied extensively, which inserts extra gates,
i.e., test points (TPs), into the circuit during the design-for-test (DFT)
phase. As finding an optimal TP position is a known NP-hard problem [4], many
methods have been proposed to build computationally feasible TPI algorithms.
The straight-forward approaches perform fault simulation to identify the RPR
faults and then insert TPs targeting on such faults [3, 5, 6]. The
approximate-measurement approaches estimate the testability by fast
approximation and insert TPs to improve testability [7, 8, 9]. However, both
of them are often ineffective on modern circuits. The fault simulation
approach requires the unacceptable runtime proportional to the size of the
circuit [10], while the accuracy of approximate measurement usually degrades
due to the reconvergence structures [11].

With the emergence of machine learning, various learning-based approaches [12,
13, 14] achieve comparable test results to the previous work. [12] predicts
the test coverage improvement of different TPs by an artificial neural network
(ANN). After that, [13] estimates the TP impact on delay fault coverage
improvement. However, the label generation relies on the exhaustive fault
simulation after inserting all possible TPs, which is expensive and
intractable for large-scale circuits. [14] proposes a graph convolutional
network (GCN) to classify nodes as either hard-to-observe or easy-to-observe.
The application of GCN to circuits is shown to be effective for automatic test
pattern generation (ATPG) TPI. Nevertheless, the labels used for model
training may not be always accurate because they are obtained from commercial
DFT tools, which in turn adopt heuristic algorithms. In theory, the model
performance is bounded by the heuristic algorithm and is sub-optimal. To
summarize, the supervised learning approach is not fully suitable for the TPI
problem.

Instead of collecting supervision for all TP candidates from the DFT tools, in
this work, we propose a novel learning-based TPI technique, namely DeepTPI,
which formulates the TPI problem as a reinforcement learning (RL) task. The
optimization objective of DeepTPI is to maximize LBIST test coverage by
inserting TPs sequentially. Compared with the prior supervised-learning based
TPI approaches, the benefits of our proposed solution are as follows: 1) The
RL-based approach is more sample-efficient than supervised learning and is
free from the dependence on the vast number of training samples; 2) The RL-
based approach can fundamentally break the upper bound of performance caused
by supervision.

In the DeepTPI formulation, we transform the circuit netlist into a graph to
naturally represent the circuit. The RL action space is defined as inserting a
TP following a certain gate over the circuit graph. With the node-level
discrete action space, our RL agent is trained with Deep Q-learning [15], and
is equipped with a novel graph-based deep Q-network (Graph-DQN) to fit the
action-value function. After aggregating the message from neighbors for
multiple iterations, the hidden state of each node is read out to predict the
expected total reward of all possible actions for this node. We set the test
coverage improvement as the reward in this TPI-for-LBIST task. The RL policy
is defined as selecting the action with the maximum expected value.We also
enhance the representation ability of our Graph-DQN by involving prior
knowledge from DeepGate [16]. In addition, we analyze the dominant factors of
testability and mimic testability by a customized attention mechanism. During
GNN aggregation, the testability-aware attention mechanism gives higher weight
to those nodes with more significant impacts on testability.

The contributions of this work are summarized as follows:

  * •

We formulate the TPI problem as a reinforcement learning task and train an RL
agent with the Deep Q-learning algorithm. To the best of our knowledge, this
is the first work applying reinforcement learning on test point insertion.

  * •

We transform the RL state into a graph and deploy a dedicated graph-based deep
Q-network (Graph-DQN) to assist RL decisions. Moreover, the general neural
representation from pre-trained DeepGate [16] is embedded into the node
feature to involve the prior circuit knowledge.

  * •

We deploy a dedicated GNN to assist RL policy decisions. By analyzing the
essence of testability, we propose a testability-aware attention mechanism in
the GNN to capture more useful information during aggregation for the TPI
task.

We organize the remaining sections as follows. Some related work about this
paper is summarized in Section II. Section III models TPI as an RL problem and
introduces the RL components. The architecture and methodology of DeepTPI are
explained in Section IV. The experimental results are shown in Section V.
Finally, Section VI concludes this paper.

##  II Related Work

###  II-A Test Point Insertion

Figure 1: Examples of Test Point Insertion(Left: AND Control Point, Middle: OR
Control Point, Right: Observation Point)

Test point insertion [3] is a circuit modification technique that adds extra
gates into circuits during the design-for-test (DFT) phase and enhances
circuit testability. As shown in Fig. 1, the test points are categorized into
two types: control points (CPs) and observation points (OPs). CPs are
typically implemented as OR gates for control-1 TPs or AND gates for control-0
TPs. During the testing, a test enable pin forces lines to their controlled
values [17]. The goal of control CPs is to increase the circuit
controllability, i.e., the probability of activating faults and sensitizing
the fault propagation paths [18]. OPs change circuit observability by
inserting pseudo primary output to the gate outputs to make faulty values on
lines more observable [19].

Although TPI has various applications in different scenarios, e.g., ATPG [20]
or analog testing [21], this work addresses TPI in the context of LBIST. On
the one hand, LBIST generates test patterns and verifies the corresponding
responses on-chip. Thus, as an in-field test technique, LBIST is in demand for
high-assurance applications, such as implantable medical devices and self-
driving vehicles. On the other hand, LBIST quality is more suffered from the
presence of RPR faults than the deterministic testing [1]. Handling the RPR
faults by TPI is known as a NP-hard problem [4]. The current heuristic TPI
approaches are still inefficient [2] and even decrease the circuit testability
in some cases [11].

Since the performance of most conventional TPI approaches degrades for the
modern circuits with complex structures, various learning-based approaches are
proposed to select TPs using advanced machine learning algorithms. [12] and
[13] estimate the quality of TPs with an artificial neural network (ANN), but
the model relies on large amounts of samples. Unlike supervised learning
approaches, the RL algorithm used in this paper trains an agent by action-
environment interaction rather than exhaustively executing all possible TP
candidates. [14] classifies each node into easy-to-observe or hard-to-observe.
However, the binary labels are collected from a heuristic testability analysis
algorithm, which is sub-optimal and bounds the performance of the resulted
model in theory. On the contrary, our proposed RL-based approach is not
limited by the upper-bound performance.

###  II-B Reinforcement Learning

Recently, reinforcement learning (RL) has achieved outstanding performance in
different applications. In general, RL is suitable for solving the problems
without apparent supervision, which is often the case in many EDA
applications. For example, getting the optimal test patterns in software-based
self-test (SBST) is impractical. Thus, [22] formulates SBST as an RL problem
and rewards the agent when a newly detected fault is reached. Besides, the
best quality of result (QoR) is hard to be produced as supervision in logic
synthesis due to the exponential number of possible optimization permutations.
[23, 24] convert logic synthesis as an RL problem, whose optimization target
is set as reducing area or depth.

In EDA, the most natural representation of circuits, intermediate RTL,
netlists, and layouts are graphs [25]. Consequently, a few RL approaches
incorporate graph neural networks as the backbones to capture the graph
structures. For instance, GCN-RL circuit designer [26] embeds the topology
graph information with GNN and uses an RL optimization algorithm to achieve
the high Figures of Merit (FoM) for automatic transistor sizing problems. [27]
proposes a GNN model to encode the information about netlist and make macro
placement decisions with another policy network. Besides, [28] and [29]
combine the RL agent with GNN to design combinatorial optimization solvers.
Our proposed DeepTPI shares the similar intuition with these works, which
learns the circuit knowledge via a GNN and conducts TPI actions based on the
learned graph embeddings.

##  III Reinforcement Learning Formulation

Figure 2: Test Point Insertion as an Markov Decision Process (MDP)

In this work, we target the test point insertion (TPI) problem, in which the
objective is to improve the test coverage under LBIST random patterns by
inserting control points and/or observation points. Such a sequential
decision-making problem can be modeled as a Markov Decision Process (MDP).
Moreover, an optimal decision strategy in such a sequential decision-making
setting can be identified by reinforcement learning (RL) methods [30]. Hence,
in this section, we formally introduce the TPI problem from a reinforcement
learning perspective, and build the connections between key elements of RL and
TPI.

Given a circuit netlist, we form a directed graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, where each gate $v$ in the circuit is
a vertex belong to $\mathcal{V}$, and $\mathbf{e}(u,v)\in\mathcal{E}$ is a
directed edge from node $u$ to node $v$. We use $T\in\mathbb{N}$ to denote the
time horizon, i.e., the number of test points to be inserted. The circuit
after inserting $t$ test points can be represented as $\mathcal{G}^{t}$.
Equipped with the above notations, we then formulate the TPI problem as an MDP
(Shown in Fig. 2), which consists of the following four key elements:

  * •

State $\mathcal{ST}$: the set of states. In TPI task, the state is reflected
as circuit with graph structure. The state is represented as the circuit at
time step $t$: $s^{t}:=\mathcal{G}^{t}\in\mathcal{ST}$.

  * •

Action $\mathcal{A}$: the set of actions that an agent can execute, i.e.,
inserting test points into the circuit. The action corresponds to inserting
one kind of TPs on the following wire of a particular gate, which can be
defined as $a^{t}:=(v,type)\in\mathcal{A}$, wherein $v$ is the selected gate
for the test point insertion and $type\in\\{\text{AND-CP},\text{OR-
CP},\text{OP}\\}$ indicates what type of test point to be inserted.

  * •

State transition function $\mathcal{F}$: Given state $s^{t}$ and an action
$a^{t}$ at time $t$, the function produces the updated state $s^{t+1}$. Since
the the circuit after an action of TPI is uniquely determined, the state
transition function is deterministic. We denote the transition function as
$s^{t+1}=\mathcal{F}(s^{t},a^{t})$.

  * •

Reward function $\mathcal{R}$: step reward
$r^{t}=\mathcal{R}(s^{t},a^{t},s^{t+1})$ caused by the corresponding action
$a^{t}$ with state transition from $s^{t}$ to $s^{t+1}$. In TPI task, we
consider the improvement of the test coverage as the reward.

As shown in Fig. 3, at each step $t$, the agent extracts information from the
current state $s^{t}$ and selects an action $a^{t}$. Then, the circuit inside
the environment is updated by the state transition function
$s^{t+1}=\mathcal{F}(s^{t},a^{t})$. The primary target to solve the MDP
problem is to train an RL agent with optimal policy $\pi$, a mapping that
outputs an action which maximizes the expected cumulative rewards. The MDP
also defines a discounting factor $\gamma^{0}$, which determine the different
weights on long-term reward and short-term reward. The overall objective of
the agent decision is to maximize the expected discounted reward:
$G=\mathbb{E}[\sum_{t=0}^{T-1}\gamma^{t}r^{t}]$, where
$\gamma^{t}=\text{Power(}\gamma^{0},t\text{)}$.

Figure 3: RL Agent - Environment Interaction in DeepTPI

In the TPI setting, the trained agent shall select the optimal positions and
insert the corresponding test points so that the maximum test coverage
improvement is achieved. We instantiate the reward function
$\mathcal{R}(s^{t},a^{t},s^{t+1})$ in Eq. (1) as test coverage improvement (TC
Imp.) after inserting $T$ TPs in total, that is the difference of test
coverage between the final circuit with $T$ TPs inserted and the initial
circuit. The reward function belongs to the terminal reward, which is nonzero
only after inserting $T$ TPs. Thus, we can set the discounting factor $\gamma$
to an arbitrary value in $[0,1)$ because the long-term or short-term
discounting does not affect the optimization objective. Ideally, the trained
RL agent selects a list of TPs with the size of $T$ to achieve globally
optimal test coverage improvement.

$r^{t}=\mathcal{R}(s^{t},a^{t},s^{t+1})=\left\\{\begin{aligned}
&0,\qquad\qquad t=0,\cdots,T-2,\\\ &TC\text{ }Imp.,\
t=T-1\end{aligned}\right.$ (1)

To approach the described objective above, we designate a combination of graph
neural network and deep Q-learning that approximates an optimal action-value
function for TPI. We discuss the methodology in detail in the following
section.

##  IV Methodology

Figure 4: The Overview of DeepTPI Agent

###  IV-A Overview of DeepTPI

Fig. 4 shows the overview of the DeepTPI RL agent. Firstly, the input circuits
are preprocessed into a unified format along with the rich node features
extracted from a pre-trained model (i.e., DeepGate [16]). More precisely,
given a pool of circuit netlists for training, we process them via an
equivalent transformation into And-Inverter Graph (AIG), wherein only three
gate types, i.e., primary input (PI), AND and NOT. The details of such
transformation are elaborated in Sec. IV-B. Besides the circuit
transformation, we present a feature-based approach to enrich the node
features. We extract the node embeddings for each gate from a pre-trained
DeepGate model, which learns the general-purpose gate embeddings (See Sec.
IV-C).

Secondly, since the TPI procedure can be formulated as an MDP with a discrete
action space as discussed in Sec. III, the value-based deep Q-learning [15]
algorithm can be applied for this task. We design a Graph-based Deep Q-Network
(Graph-DQN), instantiated as a GNN along with a readout layer. The Graph-DQN
consumes the input graphs and learns to capture the testability properties of
a logic gate in the context of the whole circuit (See Sec. IV-D). To better
embed testability by the GNN model, we analyze the requirements of faults
being detectable and propose a novel testability-aware attention mechanism in
the aggregation function. The customized attention-based aggregation function
enables differentiation of predecessors and successors according to their
contribution to fault sensitization and fault propagation, respectively (See
Sec. IV-E).

Finally, given expected values for all actions predicted by Graph-DQN, the RL
agent selects the action with the maximum expected value to be conducted. Such
pipeline is repeated under the interaction with the environment until a pre-
defined termination criterion is satisfied (e.g., hit the maximum number of
test points to be inserted). Alg. 1 provides the pseudo-code of DeepTPI.

Input: The pre-TPI circuit $ckt$, Trained value network Graph-DQN and Pre-
trained model DeepGate

Output: The post-TPI circuit $ckt^{{}^{\prime}}$

/* Initialize circuit graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ */

1 $\mathcal{G}^{0}=\text{ConvertAIGGraph(}ckt\text{)}$;

/* RL decision */

2 Define TP list $\ell$;

3 Define time-step $t=0$;

4

5while  _$t\leq\text{number of TPs}$_ do

/* Calculate the initial feature */

6 $node\\_emb^{t}=\text{DeepGate}(\mathcal{G}^{t})$;

7 $\mathbf{X}^{t}$ = Concatenate($node\\_emb^{t}$, OneHot($\mathcal{V}^{t}$))
;

8

/* Calculate expected value */

9 $\mathbf{Q}^{t}=\text{Graph-DQN}(\mathcal{G}^{t},\mathbf{X}^{t})$;

10

/* Choose action */

11 $a^{t}=\text{GetAction(}\arg\max(\mathbf{Q}^{t})\text{)}$;

12 $\ell$.append($a^{t}$);

13

/* Transit state */

14 $\mathcal{G}^{t+1}=F(\mathcal{G}^{t},a^{t})$;

15

16 end while

17

/* Generate the post-TPI circuit */

18 $ckt^{{}^{\prime}}=\text{InsertTPs(}ckt,\ell\text{)}$;

19 return $ckt^{{}^{\prime}}$;

Algorithm 1 DeepTPI Application Process

###  IV-B Unified AIG of Circuits

We opt for a unified AIG representation of circuits. Since the different
circuits in the DFT phase are mapped into standard cells from different
libraries, the gate types and local structures of the circuits are likely to
have non-uniform distribution. Such heterogeneity across circuit designs is a
challenge for GNN and RL model development. Taking the fact that any type of
logic gate can be converted into the combination of AND gate and Inverter (NOT
gate), we map circuits to their corresponding AIG counterparts. It should be
noted that the transformation process does not rely on the AIG synthesis tool
[31] because test point insertion in the DFT stage prohibits modifying the
circuit structure except for TPs. Instead, we simply map the original gates to
their equivalent And-Inverter combinations without logic optimization.
Moreover, only those gates in AIG that have the corresponding positions in
original circuits are considered TP candidates. Fig. 5 shows a toy example of
the applied transformation. Only $A,B,C,D,E$ are considered as the candidate
positions for the RL agent. $D_{1},D_{2},D_{3}$ are masked out because these
nodes in AIG format do not correspond to any gates in the original circuit.

Figure 5: Convert Circuit to AIG

There are two benefits of the AIG transformation: 1) we map the gate into the
combination of AND and NOT gates directly rather than optimizing the logic so
that the transformation is of linear complexity and can scale on large
circuits; 2) including PI, only three types of nodes are considered, which
would dramatically reduce the difficulty of RL training.

###  IV-C Features of Logic Gates from DeepGate

A natural way to assign the node features for logic gates is to use the one-
hot encoding of gate types. When PIs are taken into account, there are three
gate types in AIG: $PI$, AND and NOT. Even though such one-hot encoding is a
widely adopted convention for graph learning [32, 33], it cannot include any
specific properties of logic gates to benefit RL decision, such as the gate
behaviors and testability. With limited information on logic gates to utilize,
the RL model may struggle to learn and exposes the RL agent to a high risk of
corruption.

To augment the semantic information embedded in node features, we follow the
success of model pre-training techniques in deep learning community [34, 35],
and adopt a feature-based approach, i.e., using the pre-trained node
embeddings as the additional features to incorporate the gate semantics. To be
specific, we extract the node embeddings from a pre-trained DeepGate model
[16] and feed them as the initial node features for RL training. The task of
DeepGate is to approximate the simulated probability, i.e., the probability of
the gate being logic $1$ under random logic simulation. With strong biases
introduced into DeepGate design, the node embeddings for logic gates embed
both logic function and structural information of a circuit. We concatenate
the node embeddings from pre-trained DeepGate and the $3$-d one-hot encoding
of gate types together to construct the node feature $x_{i}$ for node $v_{i}$.
The effectiveness of the proposed feature-based pre-training is demonstrated
by the ablation study in Sec. V-E.

###  IV-D Graph-based Deep Q-Network

In the MDP formulation described in Sec. III, we define the action as
inserting a TP following candidate gate, and the state transition as modifying
the circuit with the newly inserted TP. The Q-learning algorithm is suitable
to explore an optimal policy for such MDP problem with a discrete gate-level
action space and deterministic state transition [36]. Therefore, we apply
Q-learning to RL-formulated TPI problem.

The classical Q-learning approximates the expected reward for all possible
actions based on the current state, and maintains an action-value function as
a table (also named Q-Table). Due to the increasing scale of action space in
practice, the deep Q-learning [15] introduces a value network (also named
Q-Network) to implicitly fit the action-value function. Specifically, at each
time step $t$, the Q-Network ($\mathcal{Q}$) predicts the future rewards of
all possible actions $a^{t}$ in current state $s^{t}$. The optimal policy
$\pi$ is defined as executing the action with maximum value:

$a^{t}=\pi(s^{t})=\arg\max_{a^{t}}(\mathcal{Q}(s^{t},a^{t}))$ (2)

In TPI task, since the state $s^{t}$ solely depends on a directed acyclic
graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, the action space is defined at
node-level over an arbitrary graph. To accommodate the requirements of dealing
with graph-based data, we refer to a graph neural network, and implement the
value network as the graph-based deep Q-Network (Graph-DQN) to approximate the
action value. The whole architecture is shown as the Graph-DQN value network
block in Fig. 4. We calculate the node embedding for each node for multiple
iterations by a GNN and readout the expected value with a multi-layer
perceptron (MLP).

We formally introduce the GNN structure used in Graph-DQN. The GNN propagates
the message between each node $v_{i}\in\mathcal{V}$ and its neighbors
$\mathcal{N}(i)$ with two functions: aggregation function AGGR and update
function UPDATE. The aggregation function enables the message-passing of all
nodes with arbitrary degrees. The update function combines the node feature
with the incoming message and updates the hidden state iteratively. We apply
gated recurrent neural (GRU) [37] to implement the UPDATE function. We define
the GNN computations as Eq. 3, where $h_{i}^{d}$ is the hidden state and
$d=0,1,...,D-1$ is the number of iterations. The initial hidden state
$h_{i}^{0}$ is assigned to node feature $x_{i}$. The aggregation function can
be implemented by average pooling [38] or linear transformation [39], but
these methods do not differentiate the neighbors who dominate the testability.
To mimic the essence of testability, we borrow the attention-based aggregation
function from [40]. We elaborate on the testability-aware attention mechanism
in Sec. IV-E.

$h_{i}^{d+1}=\text{UPDATE}^{d+1}(\text{AGGR}^{d+1}(\\{h_{k}^{d+1}\|k\in\mathcal{N}(i)\\}),h_{i}^{d})$
(3)

The GNN message-passing process performs for $D$ iterations. The $h_{i}^{D}$
after the node embedding of the final iteration $d=D-1$ is fed into the
readout function READOUT to produce the expected total value of all possible
actions:

$q_{i}=\text{READOUT}(h_{i}^{D})$ (4)

where $q_{i}$ is a three-dimension vector for each node $v_{i}\in\mathcal{V}$
that presents the action value when inserting the AND control point, OR
control point, or observation point. The RL agent chooses the action with the
maximal value to maximize the total reward.

We define the action selection process as following four steps:

  1. 1.

Node feature construction: The initial node feature $\mathbf{X}^{t}$ is
concatenated of the node embedding $node\\_emb^{t}$ from the pre-trained
DeepGate model and one-hot gate type encoding of each node
$\text{OneHot}(\mathcal{V}^{t})$.

$\begin{split}node\\_emb^{t}&=\text{DeepGate}(\mathcal{G}^{t})\\\
\mathbf{X}^{t}&=\text{Concatenate}(node\\_emb^{t},\text{OneHot}(\mathcal{V}^{t}))\end{split}$
(5)

  2. 2.

Value approximation: Based on the initial node feature $\mathbf{X}^{t}$ and
graph $\mathcal{G}^{t}$, the proposed Graph-DQN predicts the expected
cumulative reward $\mathbf{Q}^{t}$ for each possible action in node-level.

$\mathbf{Q}^{t}=\text{Graph-DQN}(\mathcal{G}^{t},\mathbf{X}^{t})$ (6)

  3. 3.

Action execution: The agent policy is selecting the action with the maximum
expected reward.

$a^{t}=\text{GetAction}(\arg\max(\mathbf{Q}^{t}))$ (7)

  4. 4.

State transition: The circuit structure changes after inserting the
corresponding TP. The environment updates the state to be $\mathcal{G}^{t+1}$.

$\mathcal{G}^{t+1}=F(\mathcal{G}^{t},a^{t})$ (8)

Besides, in the RL training process, the parameter $\theta$ in $\text{Graph-
DQN}_{\theta}$ is updated iteratively by:

$\begin{split}L(\theta)&=Loss(\text{Graph-
DQN}_{\theta}(s^{t},a^{t}),\mathcal{R}(s^{t},a^{t},s^{t+1})+\\\
&\gamma^{0}argmax_{a^{t+1}}(\text{Graph-
DQN}_{\hat{\theta}}^{{}^{\prime}}(s^{t+1},a^{t+1})))\end{split}$ (9)

where the target network $\text{Graph-DQN}_{\hat{\theta}}^{{}^{\prime}}$ is
another value network used as a measure of ground truth (i.e. the expected
future reward) and stabilize learning. The parameter $\hat{\theta}$ is updated
to $\theta$ every $U$ epochs. We use Mean-Squared (MSE) loss as the loss
function $Loss$.

###  IV-E Testability-Aware Attention Mechanism

In the logic circuits, when the logic gate receives a controlling value from
one of the inputs, the output value is almost independent of the other inputs
[41]. For example, the fan-in value 0 is a controlling value of AND gate and
forces the gate to be 0 no matter what the values of the other fan-in gates
are. The rule can be derived from the other types of gates. Such similar gate
property plays an important role in testability analysis. Fig. 6 shows an
example of detecting a stuck-at-1 (SA1) fault at gate $C$, where 0/1 means the
expected logic value of this line is 0, but the fault causes the value to 1.
The circuit must fulfill two conditions to enable such SA1 fault to be
detected: (a) at least one random pattern assigning logic 0 at the gate $C$,
i.e., the fault-effect (logic difference) is activated; (b) at least one path
that allows the fault-effect to propagate from $C$ to any primary outputs $E$
or $D$, i.e., the fault-effect can be observed. We assume the testability as
the probability of a gate meeting both conditions (a) and (b).

Figure 6: An Example of Stuck-at-1 Fault

The predecessor with controlling value dominates the fault activation. For
example, if there is a controlling value (logic 1) in any fan-in wire of gate
$C$, the fault cannot be activated. Intuitively, to estimate the probability
of meeting the above condition (a), we need focus on the fan-in gates with a
high probability to be logic 1. Moreover, condition (b) requires the fault-
effect being observed, no matter on which primary output. Take the fault-
effect 0/1 propagation in Fig. 6 as an example, there are two paths following
stem gate $C$. Sensitizing the path through $E$ by forcing one line to be 1 is
easier than $D$. The probability of observing this fault-effect relies only on
the difficulty of sensitizing the path through successor $E$. Therefore, the
neighbor that can easily propagate fault-effect is more noteworthy. To
summarize, the predecessors and successors play different and significant
roles in the testability of each gate.

To mimic the above properties during GNN propagation, we turn to graph
attention network [40]. Graph attention network computes the hidden
representations of each node in the graph by attending over its neighbors
following a attention mechanism. Inspired by this work, our RL value network
also follows an attention strategy. The Graph-DQN distinguishes the attention
on predecessors and successors because the predecessors determine whether the
fault-effect can be activated, and the successors affect the effect
observation. Therefore, we define the testability-aware attention mechanism in
the aggregation function AGGR as below:

$\begin{split}m_{i(pre)}^{d}&=\sum_{p\in\mathcal{P}(i)}\alpha_{(i,p)}^{d}h_{p}^{d},\\\
&\ \text{where}\
\alpha_{(i,p)}^{d}=\mathop{softmax}\limits_{p\in\mathcal{P}(i)}(w_{0}^{\top}h_{i}^{d-1}+w_{pre}^{\top}h_{p}^{d})\\\
m_{i(suc)}^{d}&=\sum_{s\in\mathcal{S}(i)}\beta_{(i,s)}^{d}h_{s}^{d},\\\ &\
\text{where}\
\beta_{(i,s)}^{d}=\mathop{softmax}\limits_{s\in\mathcal{S}(i)}(w_{0}^{\top}h_{i}^{d-1}+w_{suc}^{\top}h_{s}^{d})\end{split}$
(10)

wherein $\mathcal{P}(i)$ and $\mathcal{S}(i)$ are the predecessors and
successors of node $i$, respectively. During the training process, two
independent model parameters, $w_{pre}$ and $w_{suc}$, are used for
calculating the attention weighting coefficients $\alpha_{(i,p)}^{d}$ and
$\beta_{(i,s)}^{d}$. These two coefficients represent the appropriate
attention on aggregating information from different predecessors or
successors.

After we obtain the aggregated message $m_{i(pre)}^{d}$ and $m_{i(suc)}^{d}$,
we update them together as the output of $AGGR$ function. With the
testability-aware attention mechanism, the GNN can generate the embedding with
much more testability information for RL decisions.

##  V Experiments

In this section, we present our constructed circuit datasets for training and
testing, as well as the baseline in Sec. V-A. We elaborate the model settings
in Sec. V-B. Then, we discuss the performance comparison between DeepTPI and
the commercial DFT tool, and analyze the advantage of DeepTPI in Sec. V-C. To
explore the effectiveness of the testability-aware attention mechanism and the
feature-based pre-training, we present two ablation studies in Sec. V-D and
Sec. V-E, respectively. Finally, we analyze the computational complexity and
discuss some potential improvements in Sec. V-F.

###  V-A Circuit Dataset and Baseline

We extract 400 sub-circuits from ISCAS89 [42] and ITC99 [43], and convert them
to AIG format for RL training. Tab. I summarizes the statistics of training
circuits. # Gates denotes the number of gates in circuits, while # PIs and #
POs represent the number of primary inputs (PIs) and primary outputs (POs),
respectively. # Levels is the total number of logic levels. The test coverage
(TC) on original circuits is reported by a commercial LBIST tool under the
same volume of random test patterns, i.e., $300K$ patterns. In some cases,
especially for these circuits with high test coverage, inserting the
inappropriate test point may reduce the random test coverage. For example, the
extra AND control point on the fan-in wires of the AND gates causes the SA1
faults more hard to be activated. To explore the optimal policy avoiding the
test coverage loss for these circuits, our training dataset also includes the
circuits that can be fully tested by LBIST (TC=100.00%).

TABLE I: The Statistics of Training Circuits | # Gates | # PIs | # POs | # Levels | TC
---|---|---|---|---|---
Min. | 83 | 8 | 1 | 7 | 24.08%
Max. | 656 | 98 | 24 | 80 | 100.00%
Avg. | 201.73 | 23.87 | 7.42 | 15.77 | 90.59%

For inference, we choose eight large combinational circuits from two open-
source benchmarks, i.e., ITC [43] and EPFL [44], and compare the test coverage
reported from the state-of-the-art commercial DFT tool and DeepTPI. To examine
the generalization property of our RL approach, the size of testing circuits
varies from 3.4K to 127.4K, which is much larger than those in the training
dataset. The statistics of the testing circuits in AIG format are listed in
Tab. II. It should be noted that there is no overlap between training circuits
and testing circuits. The pre-TPI test coverage is shown in Column TC in Tab.
II.

According to practical experience, the inserted test points for LBIST coverage
improvement occupy 0.1%-2.0% extra area over the entire circuit. Typically,
there is a strong positive correlation between the number of TPs and test
coverage improvement. In the following experiments, we fix the number of
inserted test points (# TPs) as $1.0\%$ of # Gates for all testing circuits.

TABLE II: The Statistics of Testing Circuits in AIG format | Name | # Gates | # PIs | # POs | # Levels | TC
---|---|---|---|---|---|---
D1 | b15_C | 27,838 | 485 | 449 | 158 | 90.61%
D2 | b20_C | 61,667 | 522 | 507 | 165 | 90.60%
D3 | b21_C | 62,817 | 522 | 507 | 167 | 89.73%
D4 | b22_C | 91,505 | 767 | 750 | 173 | 91.70%
D5 | i2c | 3,400 | 136 | 127 | 34 | 86.11%
D6 | max | 9,439 | 512 | 129 | 333 | 52.65%
D7 | b17_C | 99,466 | 1,452 | 1443 | 234 | 86.84%
D8 | mem_ctrl | 127,353 | 1,028 | 967 | 195 | 69.95%

###  V-B Model Settings

In the Graph-DQN model configuration, we set the dimension of node hidden
state as 64 and the iteration of message passing as 10. We also involve the
universal logic gate representation pre-trained model DeepGate. The pre-
trained DeepGate keeps the same configurations and hyperparameters as the
original specification [16]. We set the dimension of node hidden state as 64
and the iteration of hidden state update as 10 for DeepGate. The DeepGate
model is trained with 10,824 subcircuits extracted from open-source
benchmarks.

TABLE III: The Model Complexity of Graph-DQN and DeepGate | Graph-DQN | DeepGate | Total
---|---|---|---
# FLOPs | 116.47 M | 60.63 M | 177.10 M
# Param. | 59.01 K | 69.13 K | 128.14 K

The model complexity is illustrated in Tab. III, where # FLOPs is the number
of floating-point operations and # Param. is the total number of trainable
parameters. The RL agent is trained for 500 episodes on each circuit in Tab.
II. We use the ADAM optimizer with the learning rate $lr=0.0001$. In the
following experiment, we keep the same configuration for all DeepTPI agents.

###  V-C Performance Comparison with Commercial DFT Tool

This section compares the TPI performance between the state-of-the-art
commercial DFT tool and our proposed DeepTPI. The user manual of the tool
indicates that the testability analysis algorithm is based on COP [7] and
pattern simulation [45].

To ensure fairness, we use the same pre-TPI circuits and assign the same
number of inserted TPs. The random test patterns are generated by the same
commercial LBIST tool with an equivalent configuration. One group of post-TPI
circuits is produced by the commercial tool and the other is generated by
sequential actions from DeepTPI. The test coverage of these two groups are
abbreviated as Com. Tool TC. and DeepTPI TC, respectively. As shown in Tab.
IV, DeepTPI outperforms the commercial DFT tool significantly. For instance,
our agent can achieve $4.78\%$ test coverage improvement (abbreviated as Imp.)
on the testing circuit D3 higher than that $0.53\%$ from the commercial DFT
tool, which reaches $9.02\times$ improvement. On average, we can achieve
$2.95\times$ test coverage improvement than the tool.

TABLE IV: The Test Coverage Improvement Comparison between DeepTPI and Commercial DFT Tool | TC | # TPs | Com. Tool TC | Imp. | DeepTPI TC | Imp.
---|---|---|---|---|---|---
D1 | 90.61% | 278 | 91.50% | 0.89% | 93.20% | 2.59%
D2 | 90.60% | 616 | 91.32% | 0.72% | 95.02% | 4.42%
D3 | 89.73% | 628 | 90.26% | 0.53% | 94.51% | 4.78%
D4 | 91.70% | 915 | 92.44% | 0.74% | 95.59% | 3.89%
D5 | 86.11% | 34 | 89.72% | 3.61% | 94.44% | 8.33%
D6 | 52.65% | 94 | 58.34% | 5.69% | 63.01% | 10.36%
D7 | 86.84% | 994 | 87.96% | 1.12% | 91.67% | 4.83%
D8 | 69.95% | 1,273 | 72.34% | 2.39% | 76.98% | 7.03%
Avg. |  |  |  | 1.96% |  | 5.78%

###  V-D Effectiveness of Testability-Aware Attention Mechanism

To demonstrate that our testability-aware attention mechanism can capture more
helpful information in the TPI task, we design an ablation study with
different aggregation configurations. We apply three different aggregators in
our RL agent: the aggregator without attention (w/o Att.), the aggregator with
normal logic-aware attention, same as [16, 33] (Nor. Att.) and the aggregator
with our proposed testability-aware attention as Sec. IV-E (DeepTPI Att.).
Except for the above aggregation function, the remaining RL components keep
the same hyperparameters.

TABLE V: The Test Coverage Improvement Comparison of Different Aggregator | TC | w/o Att. | Imp. | Nor. Att. | Imp. | DeepTPI Att. | Imp.
---|---|---|---|---|---|---|---
D1 | 90.61% | 92.62% | 2.01% | 92.75% | 2.14% | 93.20% | 2.59%
D2 | 90.60% | 91.31% | 0.71% | 92.04% | 1.44% | 95.02% | 4.42%
D3 | 89.73% | 91.60% | 1.87% | 90.79% | 1.06% | 94.51% | 4.78%
D4 | 91.70% | 93.67% | 1.97% | 92.84% | 1.14% | 95.59% | 3.89%
D5 | 86.11% | 87.67% | 1.56% | 90.21% | 4.10% | 94.44% | 8.33%
D6 | 52.65% | 58.29% | 5.64% | 59.45% | 6.80% | 63.01% | 10.36%
D7 | 86.84% | 89.84% | 3.00% | 90.76% | 3.92% | 91.67% | 4.83%
D8 | 69.95% | 75.68% | 5.73% | 75.87% | 5.92% | 76.98% | 7.03%
Avg. | 82.27% |  | 2.81% |  | 3.32% |  |  5.78%

Tab. V shows the experimental results. The test coverage improvement between
post-TPI and the pre-TPI circuit is denoted as Imp.. The RL agent without any
attention mechanism only achieves $2.81\%$ Imp. on average. This setting
performs worst because it cannot determine the impact of detecting faults of
different neighbors. Although normal attention can distinguish the dominant
neighbors, it cannot capture the synergistic effect on testability between
predecessors and successors. The normal attention also has an inferior
performance to our proposed testability-aware attention mechanism. The former
only improves $3.32\%$ test coverage on average, lower than $5.78\%$ by our
proposed attention mechanism.

To summarize, the testability-aware attention is more efficient on the TPI
task because it not only captures the dominance of neighbors but also
considers the coordination between the nodes benefiting fault sensitizing and
the nodes in the easiest fault propagation path. As a result, the agent with
testability-aware attention increases $2.06\times$ TC improvement than the
agent without attention.

###  V-E Effectiveness of Feature-Based Pre-Training Approach

To investigate the effectiveness of the feature-based pre-training scheme, we
train an RL agent without the pre-trained DeepGate model (abbreviated as w/o
Pre-Train). Different from including the node embedding by the pre-trained
DeepGate model, the initial node feature for w/o Pre-Train only contains the
$3$-d one-hot encoding of gate types. Tab. VI shows the test coverage
improvement (Imp.) by these two agents with the same number of inserted TPs.
As the customized agent (w/o Pre-Train) lacks the prior logic circuit
knowledge, it only improves $2.93\%$ test coverage on average, which is much
lower than $5.78\%$ Imp. obtained by the original agent (w/ Pre-train).

To conclude, the pre-trained model provides a more helpful gate
representation. Such abundant representation can help the agent achieve about
$1.97\times$ test coverage improvement with the same TPI overhead.

TABLE VI: The Test Coverage Improvement Comparison between w/o Pre-train and w/ Pre-train | TC | # TPs | w/o Pre-Train | Imp. | w/ Pre-train | Imp.
---|---|---|---|---|---|---
D1 | 90.61% | 278 | 91.63% | 1.02% | 93.20% | 2.59%
D2 | 90.60% | 616 | 92.26% | 1.66% | 95.02% | 4.42%
D3 | 89.73% | 628 | 91.42% | 1.69% | 94.51% | 4.78%
D4 | 91.70% | 915 | 93.18% | 1.48% | 95.59% | 3.89%
D5 | 86.11% | 34 | 89.23% | 3.12% | 94.44% | 8.33%
D6 | 52.65% | 94 | 57.49% | 4.84% | 63.01% | 10.36%
D7 | 86.84% | 994 | 90.52% | 3.68% | 91.67% | 4.83%
D8 | 69.95% | 1,273 | 75.88% | 5.93% | 76.98% | 7.03%
Avg. |  |  |  | 2.93% |  | 5.78%

###  V-F Analysis of Computational Complexity

The proposed DeepTPI utilizes modern GPUs for RL training and inference. To
give an idea of the computational complexity, we take circuit D1 as an
example. The DeepTPI takes $132.07$ seconds to insert 10 TPs on D1 (running on
Nvidia GeForce GTX 1080 Ti GPU), while the commercial DFT tool takes $12.79$
seconds to insert the same number of TPs. Overall, DeepTPI takes around
$10\times$ more runtime than the commercial tool. As TPI is a one-time effort
process in the DFT phase, the computational overhead of DeepTPI is acceptable.

We also measure the runtime for different modules of DeepTPI. Fig. 7 shows the
runtime breakdown of the DeepTPI inference on the circuit D1. The pre-trained
DeepGate and Graph-DQN take $35.62\%$ and $30.53\%$ out of the total time,
respectively. Although the Graph-DQN is more complex than DeepGate (see Tab.
III), DeepGate consumes more time as it updates the node hidden state with the
orders of the logic level. Contrary to aggregating messages level-by-level,
the Graph-DQN updates all nodes over the whole graph simultaneously. Another
time-consuming computation process is the State Transition, which takes
$28.8\%$ out of total time. The State Transition refers to the re-calculation
of both the forward logic level (from PI to PO) and backward logic level (from
PO to PI) after inserting one TP. It should be noted that maintaining logic
level only profits the pre-trained model inference, as DeepGate aggregates the
message level-by-level.

There are several potential ways to further improve the efficiency of DeepTPI.
For example, DeepTPI can be paralleled on multi-devices, which can reduce the
runtime. The number of GNN iterations can also be reduced with more training
data. Or we can insert multiple TPs in each inference round. We leave them for
future work.

Figure 7: The Runtime Breakdown of the DeepTPI Inference

##  VI Conclusion

This paper proposes DeepTPI, a test point insertion approach with deep
reinforcement learning. As the circuit can be naturally modeled as a graph and
the action is defined as inserting TP on the discrete node over the graph, we
train an agent with the combination of deep Q-learning and a graph neural
network (Graph-DQN) to approximate the value of all possible actions. We also
embed a testability-aware attention mechanism into the Graph-DQN to capture
the dominant impact on testability from both predecessors and successors. The
optimal policy is to conduct the action with the maximum predicted value.
Besides, we apply DeepGate as a pre-trained model to learn the universal gate
embedding as the prior circuit information. The experimental results prove the
effectiveness of our strategies and demonstrate that DeepTPI can achieve
better performance than the commercial DFT tool.

## References

  * [1] E. J. McCluskey, “Built-in self-test techniques,” _IEEE Design & Test of Computers_, vol. 2, no. 2, pp. 21–28, 1985.
  * [2] M. He, G. K. Contreras, D. Tran, L. Winemberg, and M. Tehranipoor, “Test-point insertion efficiency analysis for lbist in high-assurance applications,” _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , vol. 25, no. 9, pp. 2602–2615, 2017.
  * [3] M. J. Y. Williams and J. B. Angell, “Enhancing testability of large-scale integrated circuits via test points and additional logic,” _IEEE Transactions on Computers_ , vol. 100, no. 1, pp. 46–60, 1973.
  * [4] B. Krishnamurthy, “A dynamic programming approach to the test point insertion problem,” in _24th ACM/IEEE Design Automation Conference_. IEEE, 1987, pp. 695–705.
  * [5] N. Tamarapalli and J. Rajski, “Constructive multi-phase test point insertion for scan-based bist,” in _Proceedings International Test Conference 1996\. Test and Design Validity_. IEEE, 1996, pp. 649–658.
  * [6] V. S. Iyengar and D. Brand, “Synthesis of pseudo-random pattern testable designs,” in _Proceedings.’Meeting the Tests of Time’., International Test Conference_. IEEE, 1989, pp. 501–508.
  * [7] F. Brglez, “On testability of combinational networks,” 1984.
  * [8] N. A. Touba and E. J. McCluskey, “Test point insertion based on path tracing,” in _Proceedings of 14th VLSI Test Symposium_. IEEE, 1996, pp. 2–8.
  * [9] D. Das and N. A. Touba, “Reducing test data volume using external/lbist hybrid test patterns,” in _Proceedings International Test Conference 2000 (IEEE Cat. No. 00CH37159)_. IEEE, 2000, pp. 115–122.
  * [10] H.-C. Tsai, C.-J. Lin, S. Bhawmik, and K.-T. Cheng, “A hybrid algorithm for test point selection for scan-based bist,” in _Proceedings of the 34th annual Design Automation Conference_ , 1997, pp. 478–483.
  * [11] S. Roy, B. Stiene, S. K. Millican, and V. D. Agrawal, “Improved pseudo-random fault coverage through inversions: a study on test point architectures,” _Journal of Electronic Testing_ , vol. 36, no. 1, pp. 123–133, 2020.
  * [12] Y. Sun and S. Millican, “Test point insertion using artificial neural networks,” in _2019 IEEE Computer Society Annual Symposium on VLSI (ISVLSI)_. IEEE, 2019, pp. 253–258.
  * [13] S. Millican, Y. Sun, S. Roy, and V. Agrawal, “Applying neural networks to delay fault testing: Test point insertion and random circuit training,” in _2019 IEEE 28th Asian Test Symposium (ATS)_. IEEE, 2019, pp. 13–135.
  * [14] Y. Ma, H. Ren, B. Khailany, H. Sikka, L. Luo, K. Natarajan, and B. Yu, “High performance graph convolutional networks with applications in testability analysis,” in _Proceedings of the 56th Annual Design Automation Conference 2019_ , 2019, pp. 1–6.
  * [15] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski _et al._ , “Human-level control through deep reinforcement learning,” _nature_ , vol. 518, no. 7540, pp. 529–533, 2015.
  * [16] M. Li, S. Khan, Z. Shi, N. Wang, Y. Huang, and Q. Xu, “Representation learning of logic circuits,” in _2022 59th ACM/IEEE Design Automation Conference (DAC), to appear_ , 2022.
  * [17] J.-S. Yang, N. A. Touba, and B. Nadeau-Dostie, “Test point insertion with control points driven by existing functional flip-flops,” _IEEE Transactions on Computers_ , vol. 61, no. 10, pp. 1473–1483, 2011.
  * [18] Y. Sun, “Novel test point insertion applications in lbist,” 2021.
  * [19] J. Fox, “Test-point condensation in the diagnosis of digital circuits,” in _Proceedings of the Institution of Electrical Engineers_ , vol. 124, no. 2. IET, 1977, pp. 89–94.
  * [20] C. Acero, D. Feltham, F. Hapke, E. Moghaddam, N. Mukherjee, V. Neerkundar, M. Patyra, J. Rajski, J. Tyszer, and J. Zawada, “Embedded deterministic test points for compact cell-aware tests,” in _2015 IEEE International Test Conference (ITC)_. IEEE, 2015, pp. 1–8.
  * [21] J. Zhang, S. Huynh, and M. Soma, “A test point insertion algorithm for mixed-signal circuits,” in _Proceedings 17th IEEE VLSI Test Symposium (Cat. No. PR00146)_. IEEE, 1999, pp. 319–324.
  * [22] C.-Y. Chen and J.-L. Huang, “Reinforcement-learning-based test program generation for software-based self-test,” in _2019 IEEE 28th Asian Test Symposium (ATS)_. IEEE, 2019, pp. 73–735.
  * [23] W. Haaswijk, E. Collins, B. Seguin, M. Soeken, F. Kaplan, S. Süsstrunk, and G. De Micheli, “Deep learning for logic optimization algorithms,” in _2018 IEEE International Symposium on Circuits and Systems (ISCAS)_ , 2018, pp. 1–4.
  * [24] A. Hosny, S. Hashemi, M. Shalan, and S. Reda, “Drills: Deep reinforcement learning for logic synthesis,” in _2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC)_ , 2020, pp. 581–586.
  * [25] D. S. Lopera, L. Servadei, G. N. Kiprit, S. Hazra, R. Wille, and W. Ecker, “A survey of graph neural networks for electronic design automation,” in _ACM/IEEE 3rd Workshop on Machine Learning for CAD (MLCAD)_. IEEE, 2021, pp. 1–6.
  * [26] H. Wang, K. Wang, J. Yang, L. Shen, N. Sun, H.-S. Lee, and S. Han, “Gcn-rl circuit designer: Transferable transistor sizing with graph neural networks and reinforcement learning,” in _2020 57th ACM/IEEE Design Automation Conference (DAC)_. IEEE, 2020, pp. 1–6.
  * [27] A. Mirhoseini, A. Goldie, M. Yazgan, J. Jiang, E. Songhori, S. Wang, Y.-J. Lee, E. Johnson, O. Pathak, S. Bae _et al._ , “Chip placement with deep reinforcement learning,” _arXiv preprint arXiv:2004.10746_ , 2020.
  * [28] E. Khalil, H. Dai, Y. Zhang, B. Dilkina, and L. Song, “Learning combinatorial optimization algorithms over graphs,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [29] V. Kurin, S. Godil, S. Whiteson, and B. Catanzaro, “Can q-learning with graph networks learn a generalizable branching heuristic for a sat solver?” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 9608–9621, 2020.
  * [30] J. Clifton and E. Laber, “Q-learning: theory and applications,” _Annual Review of Statistics and Its Application_ , vol. 7, pp. 279–301, 2020.
  * [31] R. Brayton and A. Mishchenko, “Abc: An academic industrial-strength verification tool,” in _International Conference on Computer Aided Verification_. Springer, 2010, pp. 24–40.
  * [32] V. Thost and J. Chen, “Directed acyclic graph neural networks,” _arXiv preprint arXiv:2101.07965_ , 2021.
  * [33] M. Zhang, S. Jiang, Z. Cui, R. Garnett, and Y. Chen, “D-vae: A variational autoencoder for directed acyclic graphs,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [34] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” _arXiv preprint arXiv:1810.04805_ , 2018.
  * [35] T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell _et al._ , “Language models are few-shot learners,” _Advances in neural information processing systems_ , vol. 33, pp. 1877–1901, 2020.
  * [36] C. J. Watkins and P. Dayan, “Q-learning,” _Machine learning_ , vol. 8, no. 3, pp. 279–292, 1992.
  * [37] J. Chung, C. Gulcehre, K. Cho, and Y. Bengio, “Empirical evaluation of gated recurrent neural networks on sequence modeling,” _arXiv preprint arXiv:1412.3555_ , 2014.
  * [38] W. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [39] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” _arXiv preprint arXiv:1609.02907_ , 2016.
  * [40] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, “Graph attention networks,” _arXiv preprint arXiv:1710.10903_ , 2017.
  * [41] S. Devadas, K. Keutzer, S. Malik, and A. Wang, “Certified timing verification and the transition delay of a logic circuit,” _IEEE Transactions on Very Large Scale Integration (VLSI) Systems_ , vol. 2, no. 3, pp. 333–342, 1994\.
  * [42] F. Brglez, D. Bryan, and K. Kozminski, “Notes on the iscas’89 benchmark circuits,” _North-Carolina State University_ , 1989.
  * [43] S. Davidson, “Characteristics of the itc’99 benchmark circuits,” in _IEEE International Test Synthesis Workshop (ITSW)_ , 1999.
  * [44] L. Amarú, P.-E. Gaillardon, and G. De Micheli, “The epfl combinational benchmark suite,” in _IWLS_ , no. CONF, 2015.
  * [45] C. Schotten and H. Meyr, “Test point insertion for an area efficient bist,” in _Proceedings of 1995 IEEE International Test Conference (ITC)_. IEEE, 1995, pp. 515–523.


††thanks: M. A. N. and C. P. contributed equally to this work.††thanks: M. A.
N. and C. P. contributed equally to this work.††thanks: Correspondence should
be addressed to<EMAIL_ADDRESS>
# Two-dimensional supersolidity in a dipolar quantum gas

Matthew A. Norcia  Institut für Quantenoptik und Quanteninformation,
Österreichische Akademie der Wissenschaften, Innsbruck, Austria  Claudia
Politi  Institut für Quantenoptik und Quanteninformation, Österreichische
Akademie der Wissenschaften, Innsbruck, Austria  Institut für
Experimentalphysik, Universität Innsbruck, Austria  Lauritz Klaus  Institut
für Quantenoptik und Quanteninformation, Österreichische Akademie der
Wissenschaften, Innsbruck, Austria  Institut für Experimentalphysik,
Universität Innsbruck, Austria  Elena Poli  Institut für Experimentalphysik,
Universität Innsbruck, Austria  Maximilian Sohmen  Institut für Quantenoptik
und Quanteninformation, Österreichische Akademie der Wissenschaften,
Innsbruck, Austria  Institut für Experimentalphysik, Universität Innsbruck,
Austria  Manfred J. Mark  Institut für Quantenoptik und Quanteninformation,
Österreichische Akademie der Wissenschaften, Innsbruck, Austria  Institut für
Experimentalphysik, Universität Innsbruck, Austria  Russell Bisset  Institut
für Experimentalphysik, Universität Innsbruck, Austria  Luis Santos  Institut
für Theoretische Physik, Leibniz Universität Hannover, Germany  Francesca
Ferlaino  Institut für Quantenoptik und Quanteninformation, Österreichische
Akademie der Wissenschaften, Innsbruck, Austria  Institut für
Experimentalphysik, Universität Innsbruck, Austria

###### Abstract

Supersolidity — a quantum-mechanical phenomenon characterized by the presence
of both superfluidity and crystalline order — was initially envisioned in the
context of bulk solid helium, as a possible answer to the question of whether
a solid could have superfluid properties [1, 2, 3, 4, 5]. While supersolidity
has not been observed in solid helium (despite much effort)[6], ultracold
atomic gases have provided a fundamentally new approach, recently enabling the
observation and study of supersolids with dipolar atoms [7, 8, 9, 10, 11, 12,
13, 14, 15, 16]. However, unlike the proposed phenomena in helium, these
gaseous systems have so far only shown supersolidity along a single direction.
By crossing a structural phase transition similar to those occurring in ionic
chains [17, 18, 19, 20], quantum wires [21, 22], and theoretically in chains
of individual dipolar particles [23, 24], we demonstrate the extension of
supersolid properties into two dimensions, providing an important step closer
to the bulk situation envisioned in helium. This opens the possibility of
studying rich excitation properties [25, 26, 27, 28], including vortex
formation [29, 30, 31], as well as ground-state phases with varied geometrical
structure [7, 32] in a highly flexible and controllable system.

Figure 1:  Calculated phases of dipolar droplet array. a. In-trap ground-state
density profiles calculated using eGPE for atom numbers
$N\in[3.3,4.4,5.8]\times 10^{4}$ in the droplets and trap aspect ratios
$\alpha_{t}=f_{x}/f_{y}\in[0.33,0.35,0.39]$ (left to right). The scattering
length $a=88\,a_{0}$, where $a_{0}$ is the Bohr radius. Green dots depict the
droplet positions obtained from the variational model, assuming the same $N$
and droplet number $N_{D}$ as the eGPE. Stars connect to experimentally
observed density profiles in Fig. 2b. b. Phase diagram, obtained from our
variational model, as a function of $N$ and $\alpha_{t}$ for $f_{x}=33$ Hz,
$f_{z}=167$ Hz. Linear (two-dimensional) phases with $N_{D}$ droplets are
labelled as 1D${}_{N_{D}}$ (2D${}_{N_{D}}$).

Ultracold atoms have recently offered a fundamentally new direction for the
creation of supersolids — rather than looking for superfluid properties in a
solid system like 4He, ultracold atoms allow one to induce a crystalline
structure in a gaseous superfluid, a system which provides far greater
opportunity for control and observation. This new perspective has enabled
supersolid properties to be observed in systems with spin-orbit coupling [33]
or long-range cavity-mediated interactions [34], though in these cases the
crystalline structure is externally imposed, yielding an incompressible state.
In contrast, dipolar quantum gases of highly magnetic atoms can spontaneously
form crystalline structure due to intrinsic interactions [11, 12, 13],
allowing for a supersolid with both crystalline and superfluid excitations
[14, 15, 16]. In these demonstrations, supersolid properties have only been
observed along a single dimension, as a linear chain of phase-coherent
“droplets”, i.e. regions of high density connected by low-density bridges of
condensed atoms, confined within an elongated optical trap.

The extension of supersolidity into two dimensions is a key step towards
creating an ultracold gas supersolid that is closer to the states envisioned
in solid helium. Compared to previous studies of incoherent two-dimensional
dipolar droplet crystals [35, 8], we work with both a substantially higher
atom number $N$ and relatively strong repulsive contact interactions between
atoms. This leads to the formation of large numbers of loosely bound droplets,
enabling us to establish phase coherence in two dimensions. In our system, the
repulsive dipolar interactions between droplets facilitate a structural
transition from a linear to a two-dimensional array, analogous to the Coulomb-
interaction-mediated structural phase transitions observed with ions [17, 18,
19, 20]. Unlike ions however, our droplets are compressible and result from
the spontaneous formation of a density wave, allowing for dynamical variation
in both droplet number and size. Further, the exchange of particles between
droplets enables the spontaneous synchronization of the internal phase of each
droplet across the system, and the associated superfluid excitations [14, 15,
16].

Figure 2:  Linear to zig-zag transition in an anisotropic trap. a. We confine
and condense dipolar 164Dy atoms within an anisotropic optical dipole trap
(ODT) formed by the intersection of two laser beams. By tuning the aspect
ratio of the trap in the $x$-$y$ plane ($\alpha_{t}$), perpendicular to an
applied magnetic field $B$, we induce a transition between linear and zig-zag
configurations of droplets. b. Single-trial images of the in-trap density
profile of atoms at different $\alpha_{t}$, showing structural transition from
linear to zig-zag states, as well as an increase in droplet number for higher
$\alpha_{t}$. Stars indicate values $\alpha_{t}$ and $N$ corresponding to the
eGPE calculations of Fig. 1a. c. Atomic aspect ratio $\alpha_{a}$ versus trap
aspect ratio $\alpha_{t}$. $\alpha_{a}$ is the ratio of minor to major axes of
a two-dimensional Gaussian fit to the imaged in-trap density profile (inset).
For the supersolid droplet array (black markers) we see an abrupt change in
$\alpha_{a}$ at the critical trap aspect ratio $\alpha_{t}^{*}$, extracted
from the fit (gray line, see methods). The shape of the transition agrees well
with eGPE prediction (green diamonds, see methods). For an unmodulated
condensate (white markers), no abrupt change is evident. d. Distribution of
droplet number versus $\alpha_{t}$, showing a distinct increase in droplet
number at the transition of linear to zig-zag configurations.

Dipolar quantum gases exhibit a rich set of ground- and excited-state
phenomena due to the competition between many energetic contributions. These
include mean-field interactions of both contact and dipolar nature, quantum
fluctuations, and external confinement, parameterized by potentially
anisotropic trapping frequencies $f_{x,y,z}$. Such systems can be described
with great accuracy by using an extended Gross–Pitaevskii equation (eGPE) [36,
37, 38, 39]. Even a fine variation of the strength of these energetic
contributions can lead to dramatic qualitative changes in the state of the
system, for example enabling a transition from a uniform condensate to a
supersolid, or in our present case, from a linear supersolid to a two-
dimensional one.

Fig. 1a shows ground-state density profiles calculated across this transition
using the eGPE at zero temperature. These profiles feature arrays of high-
density droplets, immersed in a low-density coherent “halo” that establishes
phase-coherence across the system. As the trap becomes more round, the
initially linear chain of droplets acquires greater transverse structure,
eventually forming a zig-zag state consisting of two offset linear arrays.

Although the eGPE has remarkable predictive power, full simulations in three
dimensions are numerically intensive, making a global survey of the array
properties as a function of our experimental parameters difficult. To overcome
this limitation, we employ a variational ansatz that captures the key behavior
of the system, and allows us to disentangle the competing energetic
contributions. In this approach, we describe an array of $N_{D}$ droplets by
the wavefunction $\psi(\mathbf{r})=\sum_{j=1}^{N_{D}}\psi_{j}(\mathbf{r})$,
where the $j$–th droplet is assumed to be of the form:
$\psi_{j}(\mathbf{r})\propto\sqrt{N_{j}}\exp\left(-\frac{1}{2}\left(\frac{|\bm{\rho}-\bm{\rho}_{j}|}{\sigma_{\rho,j}}\right)^{r_{\rho,j}}\right)\exp\left(-\frac{1}{2}\left(\frac{|z-z_{j}|}{\sigma_{z,j}}\right)^{r_{z,j}}\right)$,
interpolating between a Gaussian and a flat-top profile characteristic of
quantum droplets [40]. For a given total number of atoms $N$ and droplet
number $N_{D}$, energy minimization provides the atom number $N_{j}$ in each
droplet, as well as their widths $\sigma_{\rho(z),j}$, exponents
$r_{\rho(z),j}$, and positions $\bm{\rho}_{j}=(x_{j},y_{j})$. Repeating this
energy minimization as a function of $N_{D}$ gives the optimal number of
droplets. This model provides a good qualitative description of the overall
phase diagram (Fig. 1b), revealing that the interplay between intra-droplet
physics and inter-droplet interaction results in a rich landscape of
structural transitions as a function of the atom number and the trap aspect
ratio $\alpha_{t}=f_{x}/f_{y}$.

Several trends are immediately visible from the phase diagram. Larger $N$ and
higher $\alpha_{t}$ generally produce states with larger numbers of droplets.
Further, as with ions, a large number of droplets favors a 2D configuration,
while tighter transverse confinement (small $\alpha_{t}$) favors 1D [17, 18,
19, 20]. A transition from 1D to 2D is thus expected when moving towards
larger $N$ or to higher $\alpha_{t}$. In stark contrast to the case of ions,
the number of droplets typically increases across the 1D to 2D transition,
implying a first-order nature, while only narrow regions in the phase diagram
may allow for a 1D-to-2D transition at constant droplet number.

The variational results are in excellent agreement with our eGPE numerics, in
terms of predicting the qualitative structure of droplet array patterns, as
shown in Fig. 1a. Slight discrepancies exist between the two theories
regarding the predicted droplet positions and the location of the 1D-to-2D
transition. This is likely because of the presence of the halo in the eGPE
simulation (and presumably in the experiment), visible in Fig. 1a, which is
not accounted for in the variational model. This halo appears to accumulate at
the ends of the trap, pushing the droplets toward the trap center and likely
increasing the effective trap aspect ratio experienced by the droplets.

To explore the 1D to 2D transition experimentally, we use a condensate of
highly magnetic 164Dy atoms confined within an anisotropic optical dipole trap
with independently tunable trap frequencies $f_{x,y,z}$. The trap, shown in
Fig. 2a, is shaped like a surf-board with the tight axis along gravity and
along a uniform magnetic field that orients the atomic dipoles and allows
tuning of the contact interaction strength. Typically, we perform evaporation
directly into our state of interest at our desired final interaction strength,
as demonstrated in Refs. [13, 41]. A combination of in-trap and time-of-flight
(TOF) imaging provides us with complementary probes of the density profile of
our atomic states, and the phase coherence across the system.

Figure 3:  Coherence in linear and zig-zag states. Upper panels show averaged
images of experimental TOF interference patterns, along with projections along
horizontal and vertical directions of average (solid black lines) and
individual images (gray lines). The vertical projection is calculated between
the dashed lines. Lower panels show interference patterns calculated for the
pictured in-trap droplet configurations (green outlines). a. Linear chain of
phase-coherent droplets, showing uniaxial modulation persisting in averaged
image (26 trials). b. Zig-zag configuration of phase-coherent droplets,
showing modulation along two directions that persists in averaged image (51
trials), and hexagonal structure. The spacing of rows in the simulation was
adjusted to approximate the observed aspect ratio of TOF image. The image
outlined in blue shows the average momentum distribution calculated from a
series of 20 variational calculations converging to slightly different droplet
configurations, showing the tendency of such fluctuations to broaden features
in the interference pattern while maintaining the underlying structure. c.
Zig-zag configuration of phase-incoherent droplets. Modulation remains in
single images, as evidenced by the spread of gray traces in projection, but
washes out in average (43 trials).

We begin by studying the transition from one to two dimensions by changing the
strength of transverse confinement provided by the trap. Our optical setup
allows us to tune $f_{y}$ from roughly 75 to 120 Hz, while leaving $f_{x}$,
$f_{z}$ nearly constant at 33(2), 167(1) Hz, and thus to vary the trap aspect
ratio $\alpha_{t}$ in the plane perpendicular to the applied magnetic field
and our imaging axis. For small $\alpha_{t}$, the atoms are tightly squeezed
transversely, and form a linear-chain supersolid (as seen in in-trap images of
Fig. 2b). As we increase $\alpha_{t}$ above a critical value
$\alpha^{*}_{t}=0.34(2)$, we observe a structural phase transition to a two-
dimensional (2D) state with two side-by-side droplets in the center of the
chain. By further increasing $\alpha_{t}$, the 2D structure extends to two
offset lines of droplets in a zig-zag configuration. The observed patterns
match well with the ground-state predictions from the eGPE calculations when
we globally fix the scattering length to 88$a_{0}$.

We obtain higher atom numbers in the more oblate traps (higher $\alpha_{t}$),
giving $N=6.5(5)\times 10^{4}$ at $\alpha_{t}=0.44$ and $N=2.5(4)\times
10^{4}$ at $\alpha_{t}=0.28$. This further facilitates the crossing of the 1D
to 2D transition, by favoring states with larger numbers of droplets in the
broader traps. In the zig-zag regime, two-dimensional modulation is clearly
visible for durations beyond one second. Further, the droplet configuration
patterns are fairly repeatable, with clear structure visible in averaged
images as shown in the inset of Fig. 2c, which is an average of 23 trials
taken over roughly two hours.

The transition from 1D to 2D is immediately visible when plotting the atomic
aspect ratio $\alpha_{a}$ versus $\alpha_{t}$, as shown in Fig. 2c. We find
that $\alpha_{a}$ undergoes a rapid change at $\alpha^{*}_{t}$, as the single
linear chain develops two-dimensional structure. For comparison, we plot
$\alpha_{a}$ measured for an unmodulated BEC, formed at a different magnetic
field, which does not feature the sharp kink present for the supersolid state.

In Fig. 2d, we show the number of droplets present for different $\alpha_{t}$.
In the 1D regime, we typically see between five and six droplets. This number
abruptly jumps up by approximately one droplet for 2D states near the
transition point, and then increases up to an average value of eight droplets
as $\alpha_{t}$ is further increased. The change in droplet number indicates
that the transition that we observe is not of simple structural nature, but is
also accompanied by a reconfiguration of atoms within the droplets, as
expected from theory (see Fig. 1).

The measurements of in-trap density presented above inform us about the
structural nature of the transition, but not about phase coherence, which is
the key distinguishing feature between an incoherent droplet crystal and a
supersolid. Previous observations of 2D droplet arrays [35] were performed in
traps where the ground state is a single droplet [8], and the observed droplet
crystal was likely a metastable state lacking inter-droplet phase coherence.
In contrast, we expect from our theoretical calculations that the 2D array is
the ground state of our surfboard-shaped trap (for
$\alpha_{t}>\alpha^{*}_{t}$), facilitating the formation of a phase-coherent,
and therefore supersolid state for our experimental parameters.

We experimentally demonstrate the supersolid nature of our 2D modulated state
using a matter-wave interference measurement, as previously used in linear
supersolid chains [11, 12, 13], (Fig. 3a). In this measurement, an array of
uniformly spaced droplets creates an interference pattern with spatial period
proportional to the inverse of the in-trap droplet spacing. The relative
internal phase of the droplets determines both the contrast and spatial phase
of the interference pattern [42]. When averaging over many interference
patterns, obtained on separate runs of the experiment, clear periodic
modulation persists for phase-coherent droplets, but averages out if the
relative droplet phases vary between experimental trials. Thus, the presence
of periodic modulation in an average TOF image provides a clear signature of
supersolidity in our system, as it indicates both periodic density modulation
and phase coherence.

Figure 3a shows an example of such an averaged interference pattern for a
linear chain. Uniaxial modulation is clearly present along the direction of
the chain, indicating a high degree of phase coherence. For comparison, we
also show the expected interference pattern calculated for a linear array of
four droplets from free-expansion calculations, showing similar structure.

For conditions where in-trap imaging shows a 2D zig-zag structure, the
averaged interference pattern exhibits clear hexagonal symmetry (Fig. 3b).
This is consistent with our expectation, and is indicative of the triangular
structure of the underlying state. To confirm that the observed modulation is
not present without phase coherence, we repeat the measurement of Fig. 3b at a
magnetic field corresponding to independent droplets, and also compute
averaged interference pattern for a zig-zag state with the phases of the
individual droplets randomized between simulated trials (Fig. 3c). In both
cases, the averaged image does not show clear periodic modulation.

By exploiting the transition between linear and zig-zag states, we have
accessed a regime where the supersolid properties of periodic density
modulation and phase coherence exist along two separate dimensions. Future
work will focus on further understanding the spectrum of collective
excitations in the full two-dimensional system [26, 27, 28, 43], where both
the crystalline structure and the exchange of particles between droplets will
play an important role. Further investigations may elucidate in more detail
the nature of the phase transitions and expected configurations in a wider
range of trap aspect ratios, as well as the role that defects play in the 2D
system, either as phase-slips in the zig-zag patterns [44, 45], or as vortices
trapped between droplets of the array [29, 30, 31].

###### Acknowledgements.

We thank the Innsbruck Erbium team and Blair Blakie for discussions. We
acknowledge R. M. W. van Bijnen for developing the code for our eGPE ground-
state simulations. Author Contributions: M.A.N, C.P., L.K., M.S., M.J.M and
F.F. contributed experimental work. E.P and R.B. performed eGPE calculations.
L.S. contributed variational model. All authors contributed to interpretation
of results and preparation of manuscript. Funding: The experimental team is
financially supported through an ERC Consolidator Grant (RARE, No. 681432), an
NFRI grant (MIRARE, No. ÖAW0600) of the Austrian Academy of Science, the
QuantERA grant MAQS by the Austrian Science Fund FWF No I4391-N. L.S and F.F.
acknowledge the DFG/FWF via FOR 2247/PI2790. M.S. acknowledges support by the
Austrian Science Fund FWF within the DK-ALM (No. W1259-N27). L.S. thanks the
funding by the Deutsche Forschungsgemeinschaft (DFG, German Research
Foundation) under Germany’s Excellence Strategy – EXC-2123 QuantumFrontiers –
390837967. M.A.N. has received funding as an ESQ Postdoctoral Fellow from the
European Union’s Horizon 2020 research and innovation programme under the
Marie Skłodowska‐Curie grant agreement No. 801110 and the Austrian Federal
Ministry of Education, Science and Research (BMBWF). M.J.M. acknowledges
support through an ESQ Discovery Grant by the Austrian Academy of Sciences. We
also acknowledge the Innsbruck Laser Core Facility, financed by the Austrian
Federal Ministry of Science, Research and Economy. Part of the computational
results presented have been achieved using the HPC infrastructure LEO of the
University of Innsbruck.

## References

  * Gross [1957] E. P. Gross, Unified theory of interacting bosons, Phys. Rev. 106, 161 (1957).
  * Gross [1958] E. P. Gross, Classical theory of boson wave fields, Annals of Physics 4, 57 (1958).
  * Andreev and Lifshitz [1969] A. F. Andreev and I. M. Lifshitz, Quantum theory of defects in crystals, Sov. Phys. JETP 29, 1107 (1969).
  * Chester [1970] G. V. Chester, Speculations on Bose–Einstein condensation and quantum crystals, Phys. Rev. A 2, 256 (1970).
  * Leggett [1970] A. J. Leggett, Can a solid be “Superfluid”?, Phys. Rev. Lett. 25, 1543 (1970).
  * Chan  _et al._ [2013] M. H.-W. Chan, R. Hallock, and L. Reatto, Overview on solid 4 he and the issue of supersolidity, Journal of Low Temperature Physics 172, 317 (2013).
  * Lu  _et al._ [2015] Z.-K. Lu, Y. Li, D. S. Petrov, and G. V. Shlyapnikov, Stable dilute supersolid of two-dimensional dipolar bosons, Phys. Rev. Lett. 115, 075303 (2015).
  * Baillie and Blakie [2018] D. Baillie and P. B. Blakie, Droplet crystal ground states of a dipolar bose gas, Phys. Rev. Lett. 121, 195301 (2018).
  * Roccuzzo and Ancilotto [2019] S. M. Roccuzzo and F. Ancilotto, Supersolid behavior of a dipolar bose-einstein condensate confined in a tube, Phys. Rev. A 99, 041601 (2019).
  * Boninsegni and Prokof’ev [2012] M. Boninsegni and N. V. Prokof’ev, Colloquium: Supersolids: What and where are they?, Rev. Mod. Phys. 84, 759 (2012).
  * Tanzi  _et al._ [2019a] L. Tanzi, E. Lucioni, F. Famà, J. Catani, A. Fioretti, C. Gabbanini, R. N. Bisset, L. Santos, and G. Modugno, Observation of a dipolar quantum gas with metastable supersolid properties, Phys. Rev. Lett. 122, 130405 (2019a).
  * Böttcher  _et al._ [2019] F. Böttcher, J.-N. Schmidt, M. Wenzel, J. Hertkorn, M. Guo, T. Langen, and T. Pfau, Transient supersolid properties in an array of dipolar quantum droplets, Phys. Rev. X 9, 011051 (2019).
  * Chomaz  _et al._ [2019] L. Chomaz, D. Petter, P. Ilzhöfer, G. Natale, A. Trautmann, C. Politi, G. Durastante, R. M. W. van Bijnen, A. Patscheider, M. Sohmen, M. J. Mark, and F. Ferlaino, Long-lived and transient supersolid behaviors in dipolar quantum gases, Phys. Rev. X 9, 021012 (2019).
  * Guo  _et al._ [2019] M. Guo, F. Böttcher, J. Hertkorn, J.-N. Schmidt, M. Wenzel, H. P. Büchler, T. Langen, and T. Pfau, The low-energy goldstone mode in a trapped dipolar supersolid, Nature 574, 386 (2019).
  * Natale  _et al._ [2019] G. Natale, R. M. W. van Bijnen, A. Patscheider, D. Petter, M. J. Mark, L. Chomaz, and F. Ferlaino, Excitation spectrum of a trapped dipolar supersolid and its experimental evidence, Phys. Rev. Lett. 123, 050402 (2019).
  * Tanzi  _et al._ [2019b] L. Tanzi, S. Roccuzzo, E. Lucioni, F. Famà, A. Fioretti, C. Gabbanini, G. Modugno, A. Recati, and S. Stringari, Supersolid symmetry breaking from compressional oscillations in a dipolar quantum gas, Nature 574, 382 (2019b).
  * Birkl  _et al._ [1992] G. Birkl, S. Kassner, and H. Walther, Multiple-shell structures of laser-cooled 24 mg+ ions in a quadrupole storage ring, Nature 357, 310 (1992).
  * Raizen  _et al._ [1992] M. G. Raizen, J. M. Gilligan, J. C. Bergquist, W. M. Itano, and D. J. Wineland, Ionic crystals in a linear paul trap, Phys. Rev. A 45, 6493 (1992).
  * Fishman  _et al._ [2008] S. Fishman, G. De Chiara, T. Calarco, and G. Morigi, Structural phase transitions in low-dimensional ion crystals, Phys. Rev. B 77, 064111 (2008).
  * Shimshoni  _et al._ [2011] E. Shimshoni, G. Morigi, and S. Fishman, Quantum zigzag transition in ion chains, Phys. Rev. Lett. 106, 010401 (2011).
  * Hew  _et al._ [2009] W. K. Hew, K. J. Thomas, M. Pepper, I. Farrer, D. Anderson, G. A. C. Jones, and D. A. Ritchie, Incipient formation of an electron lattice in a weakly confined quantum wire, Phys. Rev. Lett. 102, 056804 (2009).
  * Mehta  _et al._ [2013] A. C. Mehta, C. J. Umrigar, J. S. Meyer, and H. U. Baranger, Zigzag phase transition in quantum wires, Phys. Rev. Lett. 110, 246802 (2013).
  * Astrakharchik  _et al._ [2008] G. E. Astrakharchik, G. Morigi, G. De Chiara, and J. Boronat, Ground state of low-dimensional dipolar gases: Linear and zigzag chains, Phys. Rev. A 78, 063622 (2008).
  * Ruhman  _et al._ [2012] J. Ruhman, E. G. Dalla Torre, S. D. Huber, and E. Altman, Nonlocal order in elongated dipolar gases, Phys. Rev. B 85, 125121 (2012).
  * Santos  _et al._ [2003] L. Santos, G. V. Shlyapnikov, and M. Lewenstein, Roton-maxon spectrum and stability of trapped dipolar bose-einstein condensates, Phys. Rev. Lett. 90, 250403 (2003).
  * Ronen  _et al._ [2007] S. Ronen, D. C. E. Bortolotti, and J. L. Bohn, Radial and angular rotons in trapped dipolar gases, Phys. Rev. Lett. 98, 030406 (2007).
  * Wilson  _et al._ [2008] R. M. Wilson, S. Ronen, J. L. Bohn, and H. Pu, Manifestations of the roton mode in dipolar bose-einstein condensates, Phys. Rev. Lett. 100, 245302 (2008).
  * Bisset  _et al._ [2013] R. N. Bisset, D. Baillie, and P. B. Blakie, Roton excitations in a trapped dipolar bose-einstein condensate, Phys. Rev. A 88, 043606 (2013).
  * Gallemí  _et al._ [2020] A. Gallemí, S. M. Roccuzzo, S. Stringari, and A. Recati, Quantized vortices in dipolar supersolid bose-einstein-condensed gases, Phys. Rev. A 102, 023322 (2020).
  * Roccuzzo  _et al._ [2020] S. M. Roccuzzo, A. Gallemí, A. Recati, and S. Stringari, Rotating a supersolid dipolar gas, Phys. Rev. Lett. 124, 045702 (2020).
  * Ancilotto  _et al._ [2020] F. Ancilotto, M. Barranco, M. Pi, and L. Reatto, Vortex properties in the extended supersolid phase of dipolar bose-einstein condensates, arXiv preprint arXiv:2012.15157 (2020).
  * Zhang  _et al._ [2019] Y.-C. Zhang, F. Maucher, and T. Pohl, Supersolidity around a critical point in dipolar bose-einstein condensates, Phys. Rev. Lett. 123, 015301 (2019).
  * Li  _et al._ [2017] J.-R. Li, J. Lee, W. Huang, S. Burchesky, B. Shteynas, F. Ç. Top, A. O. Jamison, and W. Ketterle, A stripe phase with supersolid properties in spin–orbit-coupled Bose-–Einstein condensates, Nature 543, 91 (2017).
  * Léonard  _et al._ [2017] J. Léonard, A. Morales, P. Zupancic, T. Esslinger, and T. Donner, Supersolid formation in a quantum gas breaking a continuous translational symmetry, Nature 543, 87 (2017).
  * Kadau  _et al._ [2016] H. Kadau, M. Schmitt, M. Wenzel, C. Wink, T. Maier, I. Ferrier-Barbut, and T. Pfau, Observing the rosensweig instability of a quantum ferrofluid, Nature 530, 194 (2016).
  * Ferrier-Barbut  _et al._ [2016] I. Ferrier-Barbut, H. Kadau, M. Schmitt, M. Wenzel, and T. Pfau, Observation of quantum droplets in a strongly dipolar bose gas, Phys. Rev. Lett. 116, 215301 (2016).
  * Chomaz  _et al._ [2016] L. Chomaz, S. Baier, D. Petter, M. J. Mark, F. Wächtler, L. Santos, and F. Ferlaino, Quantum-fluctuation-driven crossover from a dilute bose-einstein condensate to a macrodroplet in a dipolar quantum fluid, Phys. Rev. X 6, 041039 (2016).
  * Wächtler and Santos [2016] F. Wächtler and L. Santos, Quantum filaments in dipolar bose-einstein condensates, Phys. Rev. A 93, 061603 (2016).
  * Bisset  _et al._ [2016] R. N. Bisset, R. M. Wilson, D. Baillie, and P. B. Blakie, Ground-state phase diagram of a dipolar condensate with quantum fluctuations, Phys. Rev. A 94, 033619 (2016).
  * Lavoine and Bourdel [2020] L. Lavoine and T. Bourdel, 1d to 3d beyond-mean-field dimensional crossover in mixture quantum droplets (2020), arXiv:2011.12394 [cond-mat.quant-gas] .
  * Sohmen  _et al._ [2021] M. Sohmen, C. Politi, L. Klaus, L. Chomaz, M. J. Mark, M. A. Norcia, and F. Ferlaino, Birth, life, and death of a dipolar supersolid, arXiv preprint arXiv:2101.06975 (2021).
  * Hadzibabic  _et al._ [2004] Z. Hadzibabic, S. Stock, B. Battelier, V. Bretin, and J. Dalibard, Interference of an array of independent Bose–Einstein condensates, Phys. Rev. Lett. 93, 180403 (2004).
  * Schmidt  _et al._ [2021] J.-N. Schmidt, J. Hertkorn, M. Guo, F. Böttcher, M. Schmidt, K. S. Ng, S. D. Graham, T. Langen, M. Zwierlein, and T. Pfau, Roton excitations in an oblate dipolar quantum gas, arXiv preprint arXiv:2102.01461 (2021).
  * Pyka  _et al._ [2013] K. Pyka, J. Keller, H. Partner, R. Nigmatullin, T. Burgermeister, D. Meier, K. Kuhlmann, A. Retzker, M. B. Plenio, W. Zurek, _et al._ , Topological defect formation and spontaneous symmetry breaking in ion coulomb crystals, Nature communications 4, 1 (2013).
  * Ulm  _et al._ [2013] S. Ulm, J. Roßnagel, G. Jacob, C. Degünther, S. Dawkins, U. Poschinger, R. Nigmatullin, A. Retzker, M. Plenio, F. Schmidt-Kaler, _et al._ , Observation of the kibble–zurek scaling law for defect formation in ion crystals, Nature communications 4, 1 (2013).
  * Trautmann  _et al._ [2018] A. Trautmann, P. Ilzhöfer, G. Durastante, C. Politi, M. Sohmen, M. J. Mark, and F. Ferlaino, Dipolar quantum mixtures of erbium and dysprosium atoms, Phys. Rev. Lett. 121, 213601 (2018).

##  Appendix A Methods

Experimental apparatus and protocols: Our experimental apparatus has been
described in detail in Ref. [46]. Here, we evaporatively prepare up to
$N=6.5(5)\times 10^{4}$ condensed 164Dy atoms in a crossed optical dipole trap
formed at the intersection of two beams derived from the same $1064$ nm laser,
although detuned in frequency to avoid interference. One beam (the static ODT)
has an approximately $60\text{\,}\mathrm{\SIUnitSymbolMicro m}$ waist. The
second (the scanning ODT) has an $18\text{\,}\mathrm{\SIUnitSymbolMicro m}$
waist, whose position can be rapidly scanned horizontally at 250 kHz to create
a variably anisotropic time-averaged potential. By tuning the power in each
beam, and the scanning range of the scanning ODT, we gain independent control
of the trap frequencies in all three directions. The two trapping beams
propagate in a plane perpendicular to gravity, and cross at a
$45\text{\,}\mathrm{\SIUnitSymbolDegree}$ angle, which leads to the rotation
of the zig-zag state at high $\alpha_{t}$ visible in Fig. 2b.

We apply a uniform magnetic field oriented along gravity and perpendicular to
the intersecting dipole traps, with which we can tune the strength of contact
interactions between atoms. This allows us to create unmodulated Bose-Einstein
condensates, supersolid states, or states consisting of independent droplets
at fields of $B=$ 23.2 G, 17.92 G, and 17.78 G, respectively.

Details of our imaging setup are provided in Ref. [41]. In-trap and TOF images
are performed along the vertical direction (along $B$ and gravity), using
standard phase-contrast and absorption techniques, respectively. The
resolution of our in-trap images is approximately one micron. We use a $36$ ms
TOF duration for imaging interference patterns.

Atom number: We extract the condensed atom number $N$ from absorption imaging
performed along a horizontal direction in a separate set of experimental
trials under otherwise identical experimental conditions. This allows for a
larger field of view, and better fitting of thermal atoms. $N$ is determined
by subtracting the fitted thermal component from the total absorption signal.

For comparison between experiment and theory, and between the variational and
eGPE theory methods, we associate $N$ with the number of atoms in the
droplets, and not in the diffuse halo that surrounds the droplets. From
simulation of TOF expansion, we find that the halo is repelled at early
expansion times, and is likely indistinguishable from the thermal cloud in our
TOF measurements. While it is possible that some of the halo is counted in
$N$, we neglect this possibility and assume that $N$ includes only atoms
within droplets.

Scattering length: The positions of phase boundaries between different droplet
configurations are quite sensitive to the scattering length $a$, which is not
known with high precision in our range of magnetic fields. For all theory, we
use a value of $a=88\,a_{0}$, where $a_{0}$ is the Bohr radius, as this value
provides good agreement between experiment and theory for the 1D-to-2D
transition point.

Extracting critical aspect ratio: The critical aspect ratio $\alpha^{*}_{t}$
is extracted from fit to the function $\alpha_{a}=\alpha_{0}$ for
$\alpha_{t}<\alpha^{*}_{t}$,
$\alpha_{a}=\sqrt{\alpha_{0}^{2}+b(\alpha_{t}-\alpha^{*}_{t})^{2}}$ for
$\alpha_{t}>\alpha^{*}_{t}$, where $\alpha^{*}_{t}$, $\alpha_{0}$, and $b$ are
fit parameters. The error bars reported in Fig. 2c represent the standard
error on the mean, and are smaller than the markers on most points.

Interference patterns: The predicted interference patterns of Fig. 3 are
calculated by assuming free expansion of Gaussian droplets. In reality, the
droplets are probably not Gaussian, and interactions during TOF expansion may
modify the interference pattern. However, the droplet shape primarily effects
the envelope of the interference pattern, which is not our primary interest
here, and from eGPE simulations, we expect the effects of interactions to be
minor, provided that the droplets become unbound in a time short compared to
the TOF, which we verify by both looking at shorter TOFs and comparing the
fringe spacing observed in TOF with that expected from the in-trap droplet
spacing. The positions and size of the droplets are tuned to provide
illustrative interference patterns.

Droplet number: We extract the droplet number from our in-trap images using a
peak-finding algorithm applied to smoothed images. The algorithm finds the
local maxima above a threshold, which is chosen to be $40\%$ of the overall
peak value. Each in-trap density distribution is classified as linear array or
2D zig-zag based on the atomic aspect ratio. Finally, the counts with a given
droplet number are normalized by the total number of trials to get the
probability shown in Fig. 2d. Fluctuations in the number of atoms in a given
trial can push droplets above or below the threshold value, contributing to
the spread in extracted droplet number for a given $\alpha_{t}$.