# Safe and Robust Motion Planning for Dynamic Robotics via Control Barrier
Functions

Aniketh Manjunath and Quan Nguyen This work is supported by USC Viterbi School
of Engineering startup funds.A. Manjunath is with the Department of Computer
Science, University of Southern California, Los Angeles, California, 90089,
<EMAIL_ADDRESS>Nguyen is with the Department of Aerospace and
Mechanical Engineering, University of Southern California, Los Angeles,
California, 90089<EMAIL_ADDRESS>
###### Abstract

Control Barrier Functions (CBF) are widely used to enforce the safety-critical
constraints on nonlinear systems. Recently, these functions are being
incorporated into a path planning framework to design safety-critical path
planners. However, these methods fall short of providing a realistic path
considering both the algorithm’s run-time complexity and enforcement of the
safety-critical constraints. This paper proposes a novel motion planning
approach using the well-known Rapidly Exploring Random Trees (RRT) algorithm
that enforces both CBF and the robot Kinodynamic constraints to generate a
safety-critical path. The proposed algorithm also outputs the corresponding
control signals that resulted in the obstacle-free path. The approach also
allows considering model uncertainties by incorporating the robust CBF
constraints into the proposed framework. Thus, the resulting path is free of
any obstacles and accounts for the model uncertainty from robot dynamics and
perception. Result analysis indicates that the proposed method outperforms
various conventional RRT-based path planners, guaranteeing a safety-critical
path with minimal computational overhead. We present numerical validation of
the algorithm on the Hamster V7 robot car, a micro autonomous Unmanned Ground
Vehicle that performs dynamic navigation on an obstacle-ridden path with
various uncertainties in perception noises and robot dynamics.

##  I INTRODUCTION

Path planning is a fundamental problem in robotics that involves moving a
robot from an initial configuration to a goal configuration while avoiding
obstacles along the way. For efficient navigation of autonomous mobile robots,
we need an effective path planning algorithm that runs in real-time. As the
search space is continuous, it is challenging to use the shortest path
algorithms like Dijkstra’s [1], or A* [2] from graph theory. One of the
commonly used approaches is the Rapidly Exploring Random Trees (RRT)
algorithm, which iteratively builds the path by randomly sampling the search
space [3]. Although RRTs do not guarantee an optimal solution, it is
relatively faster than other path planning algorithms. However, some robotic
systems use a heuristic [4, 5, 6, 7] or potential field [8, 9, 10] approach to
path planning. For autonomous systems with dynamic constraints, heuristic-
based methods fall short on response time and cannot look ahead, resulting in
instability and non-optimal paths. Agent-based RTT such as RRT* [11] and
RRT*-smart [12] improves the quality of the path, but this comes at the cost
of computation efficiency. Constrained RRT algorithms find various
applications such as robotic manipulation [13], or quadcopter navigation [14],
etc. Research on complex methods such as Probabilistic Roadmaps [15], Machine
Learning-based path planning approach [16], Particle Swarm Optimization [17]
are gaining high interests, but present high computational complexities.

Robot path planning has been under constant development, and it is challenging
to devise algorithms that can ensure stability while satisfying safety-
critical constraints for nonlinear systems. Recently, Control Barrier
Functions (CBF) [18] was introduced to effectively address these constraints
for nonlinear systems. The approach has been successfully validated in
different application including autonomous vehicle [19, 20], or bipedal
locomotion [21, 22]. However, this is a feedback control framework and it does
not consider long-term planning under the presence of multiple obstacles.
Recently, a QP-formulation was introduced to enforce CBF constraints on the
RRT algorithm to achieve obstacle avoidance [23]. However, this work simulates
the closed-loop system using CBF control inside the planning framework,
therefore computationally expensive.

In this work, we proposed an effective framework to incorporate CBF
constraints into the RRT motion planning approach to address the problem of
dynamic robotics navigating in cluttered environments. Our work only considers
CBF as a constraint of the RRT algorithms and therefore is balanced between
safety guarantee and computation efficiency. In addition, this framework also
allows us to incorporate our prior work on robust CBF [24] into this proposed
approach to address the problem of motion planning under model uncertainty.

Following are the main contributions of this paper:

  * •

Introduction of a new technique on efficient path planning based on RRT and
Kinodynamic Barrier Function (KBF) for improving the efficiency and quality of
the path planning framework.

  * •

Introduction of a new technique on robust motion planning based on RRT and
robust KBF for a flexible and systematic approach to address model
uncertainties.

  * •

Combination of robust motion planning and real-time safety-critical control to
improve both high-level planning and real-time collision avoidance for dynamic
robotics.

  * •

Application to the problem of robust path planning and control for collision
avoidance of autonomous vehicles under different levels of uncertainties.

The rest of the paper is organized as follows. In Section II, we revisit the
Quadratic Program (QP) formulation of Control Lyapunov Functions and Control
Barrier Functions. This section also provides an overview of the Rapidly
Exploring Random Trees (RRT) algorithm. We then present in Section III the
proposed safety-critical path planner, followed by the integration of
robustness into the same planning framework. Section IV presents the numerical
validation of the proposed work with the application to autonomous vehicles.
Here, we also discuss the key advantages of the proposed work. Finally, we end
with the concluding remarks.

##  II BACKGROUND

In this section, we present the details of car dynamics, QP formulation of
different controllers followed by the RRT algorithm, all necessary features
required for establishing the proposed work.

###  II-A Car Model

We consider the bicycle model for car-like vehicles. We model the state of the
robot as:

$\displaystyle z=\begin{bmatrix}x_{p}&y_{p}&\theta&v\end{bmatrix}^{T}$ (1)
$\displaystyle\dot{z}=\begin{bmatrix}v\;cos\theta&v\;sin\theta&\;{\color[rgb]{0,0,0}v\frac{tan(\psi)}{L}}&a\end{bmatrix}^{T}$
(2)

Here $x_{p},y_{p},\theta,v$ corresponds to the robot’s position, heading, and
velocity, respectively, while $\psi$, $L$, and $a$ represent the steering
angle, robot length, and acceleration, respectively. We define control $u$
with $c=\tan(\psi)/L$ as:

$u=[c,a]^{T}.$ (3)

Using a simple transformation we define
$x=\begin{bmatrix}x_{1}&x_{2}\end{bmatrix}^{T}$ with
$x_{1}=\begin{bmatrix}x_{p}&y_{p}\end{bmatrix}^{T}$ and
$x_{2}=\begin{bmatrix}v_{x}&v_{y}\end{bmatrix}^{T}$.

By computing the derivatives
$\dot{x}_{2}=\begin{bmatrix}\dot{v}_{x}&\dot{v}_{y}\end{bmatrix}^{T}$, we get:

$\displaystyle\dot{x}_{2}=\begin{bmatrix}-v^{2}\sin{\theta}&\cos{\theta}\\\
v^{2}\cos{\theta}&\sin{\theta}\end{bmatrix}\times\begin{bmatrix}\dfrac{\tan{\psi}}{L}\\\
a\end{bmatrix}.$ (4)

The system dynamics now become:

$\dot{x}_{1}=x_{2}\;;\;\dot{x}_{2}=f(x)+g(x)u,$ (5)

where

$f(x)=\begin{bmatrix}0\\\ 0\end{bmatrix}\text{ and
}g(x)=\begin{bmatrix}-v^{2}\sin{\theta}&\cos{\theta}\\\
v^{2}\cos{\theta}&\sin{\theta}\end{bmatrix}.$ (6)

We now can apply input-ouput linearization [25] using the following pre-
control law:

$u=g(x)^{-1}(\mu-f(x)).$ (7)

Given the current state $x$ and a reference state $x_{rm}$, we define error
as:

$e=x_{rm}-x.$ (8)

Deriving the I-O linearized dynamics, we get:

$\dot{e}=Fe+G\mu,$ (9)

where

$\text{F = }\begin{bmatrix}0&I\\\ 0&0\\\ \end{bmatrix}\text{ and G =
}\begin{bmatrix}0\\\ I\\\ \end{bmatrix}.$ (10)

The system can be stabilized using a simple PD control:

$\mu_{pd}=\begin{bmatrix}-K_{P}&-K_{D}\end{bmatrix}e,$ (11)

with $K_{P}$ and $K_{D}$ as proportional and derivative constants.

###  II-B Control Lyapunov Function (CLF)

Having presented the dynamics for autonomous vehicles, we now present a
feedback control framework based con CLF-CBF-QP to guarantee stability and
safety-critical constraints for the control system.

We first begin by generating a Control Lyapunov Function (CLF) [25], by
solving for $P$ in the following Lyapunov equation:

$A^{T}P+PA=-Q,$ (12)

where

$Q=I\text{ ; }A=\begin{bmatrix}0&I\\\ -K_{P}&-K_{D}\end{bmatrix}.$ (13)

We now define the CLF for our system (5) as:

$\displaystyle V=e^{T}Pe$ (14) $\displaystyle L_{f}V=e^{T}(F^{T}P+PF)e$ (15)
$\displaystyle L_{g}V=2e^{T}PG$ (16)

where $L_{f}$ and $L_{g}$ are the Lie derivatives of functions $f$ and $g$,
respectively. This gives us the CLF condition that enforces stability on the
system:

$L_{f}V+L_{g}V\mu+e^{T}Qe\leq 0.$ (17)

By enforcing equation (17) in our Quadratic Program, we have our CLF-QP
controller:

CLF-QP:

$\displaystyle\min||\mu-\mu_{pd}||^{2}$ $\displaystyle\text{s.t.}-\infty\leq
L_{g}V\mu\leq-L_{f}V-e^{T}Qe\text{ (\bf CLF\bf)}$

###  II-C Exponential Control Barrier Function (CBF)

The CLF-QP controller discussed earlier only assures stability and does not
guarantee safety-critical constraints, such as collision avoidance. Given the
current position of the robot $({x_{p}},{y_{p}})$ and obstacle of known radius
$r_{o}$ at position $({x_{o}},{y_{o}})$, we can define the Barrier function
$B(x)$ that strictly enforces safety-critical constraint [26]. For simplicity,
we set a safety boundary for the car using a circle with the radius $r_{r}$.
Hence, the safety distance between the robot and the obstacle is set to
$r=r_{o}+r_{r}$. In this paper, we will use this distance to maintain
collision-free between the car and surrounding obstacles. We then can enforce
safety using Exponential CBF [26] as follows:

In order to guarantte:

$\displaystyle B(x)=({x_{p}}-{x_{o}})^{2}+({y_{p}}-{y_{o}})^{2}-r^{2}\geq 0,$
(18)

we can enforce the following constraint:

${B_{1}}(x)={\dot{B}(x)}+{\gamma_{1}}{B(x)}\geq
0\;\;\;(with\;\;{\gamma_{1}}>0),$ (19)

where

$\displaystyle\dot{B}(x)=2(x_{p}-x_{o})v_{x}+2(y_{p}-y_{o})v_{y}.$ (20)

By repeating the step one more time, we arrive at the following CBF condition:

$\dot{B_{1}}(x)+{\gamma_{2}}{B_{1}(x)}\geq 0\;\;\;\;(with\;\;{\gamma_{2}}>0),$
(21)

where

$\dot{B}_{1}(x)=\gamma_{1}\dot{B}(x)+2v_{x}^{2}+2v_{y}^{2}+2\begin{bmatrix}x_{p}-x_{o}&y_{p}-y_{o}\end{bmatrix}\mu.$
(22)

Adding (21) into the set of QP constraints, we derive our CLF-CBF-QP
Controller:

CLF-CBF-QP:

$\displaystyle\min||\mu-\mu_{pd}||^{2}+Pd^{2}$
$\displaystyle\text{s.t.}-\infty\leq L_{f}V+L_{g}V\mu+e^{T}Qe\leq d\text{ (\bf
CLF\bf)}$ $\displaystyle
0\leq\dot{B_{1}}(x)+\gamma_{2}B_{1}(x)\leq\infty\text{ (\bf CBF\bf)}$

Here, the additional term $Pd^{2}$ is introduced to relax the bound of the CLF
condition for satisfying conflicting additional constraints. Here, $d>0$ and
$P$ is a large positive number that represents the penalty for relaxing the
inequality constraints.

###  II-D Rapidly-exploring Random Tree (RRT)

In the previous sections, we discussed various controllers that minimize error
while enforcing stability and safety-critical conditions. To compute error
$e$, we need a reference model $x_{rm}$, see equation (8). Given the start and
goal state, we need a path planner that returns the required reference
$x_{rm}$. Although RRTs does not guarantee optimality, they are comparatively
faster than other methods. Hence, in this work, we use RRTs for path planning,
see Algorithm 1.

Within the defined search space, the RRT algorithm grows a tree from start to
goal by performing the following three functions where each node is associated
with the state as given by the system dynamics:

  * •

get_random_sample returns a random sample in the search space with a uniform
probability distribution.

  * •

get_nearest_neighbor returns the nearest neighbor of the random sample from
the set of previously visited samples of the tree based on the Euclidean
distance.

  * •

extend_sample checks if the path from the nearest neighbor node and the random
sample is free of obstacles. The Auxillary function check_collision is used to
determine whether the new state violates the safety constraints. If the
constraint is satisfied, the trees grow by constant step-size in the direction
of the random sample. In presence of more than one obstacle, this step is
repeated for each obstacle and the new state is considered valid if it
satisfies the safety constraints for all obstacles.

The RRT tree iteratively grows until it reaches the goal state. As an added
measure, to limit the time, the total number of iterations is limited. In the
next section, we will use the knowledge of CLF and CBF controllers to
formulate our safety-critical path planner.

Algorithm 1 RRT

function RRT($start_{state},goal_{state},step\\_size,obstacles$)

$tree\leftarrow(null,start_{state})$

$s\leftarrow step\\_size$

$o\leftarrow obstacles$

while $tree.visited(goal_{state})$ is $False$ do

$node_{r}\leftarrow\bf get\\_random\\_sample()\bf$

$node_{n}$ $\leftarrow\bf extend\\_sample\bf$($tree,node_{r},s,o$)

if $node_{n}$ it not  $null$

$tree.add(node_{n},node_{r})$

end while

return $tree$

end function

function extend_sample($tree,node_{r},s,o$)

$node_{n}$ $\leftarrow\bf get\\_nearest\\_neighbor\bf$($tree,node_{r}$)

if $\bf{check\\_collision}$ $(node_{n},node_{r},o)$

return $null$$\triangleright$ path has obstacles

else

return $node_{n}$$\triangleright$ path is obstacle free

end function

##  III PROPOSED WORK

Having presented the background on RRTs and various controllers, this section
presents our proposed work on designing a path planner that incorporates
safety-critical constraints into the path planning framework. We introduce a
safety-critical path planner that runs in real-time, even under the influence
of uncertainties. We first present RRT-KBF aimed at improving the efficiency
and quality of the path planning framework, followed by Robust RRT-KBF that
adds robustness to the previous method.

###  III-A RRT with Kinodynamic Barrier Function (RRT-KBF)

Tracing back to the RRT algorithm, the first step involves fetching a random
sample. Given the current state and the random sample, we check if the path
connecting them is safe. A QP-solver can be used to find an optimal control
$\mu$ that enforces CBF constraints [23]. However, using the QP-solver for
every iteration significantly delays the convergence of RRT. Therefore, we
propose an alternative method for finding the safety-critical control, see
Algorithm 2. We first select a random node from the set of visited tree nodes.
Owning to the random nature of RRT, we also generate a random control $u$ from
a uniform distribution of kinodynamically constrained control. The required
control (3) is obtained from:

$u=\begin{bmatrix}\frac{\tan\psi}{L}\\\
a\end{bmatrix}=\begin{bmatrix}uniform\;(\frac{-\tan\psi_{max}}{L},\frac{\tan\psi_{max}}{L})\\\
uniform\;(0,a_{max})\end{bmatrix},$ (23)

where $L$, $\psi_{max}$, and $a_{max}$ are the length, maximum steering angle,
and acceleration of the robot. Given a random state and the random control
$u$, we determine if the control satisfies the CBF constraints (21). If the
control $u$ satisfies the safety-critical condition, we apply the control $u$
for a fixed time step $dt$ to reach the new state. This process repeats until
we reach the goal state. By preserving the random nature of RRT, the proposed
algorithm can achieve a faster path that satisfies the safety-critical
constraint.

By introducing the CBF constraints (21) in the exploration phase of RRT, the
proposed work ensures that every valid state of the tree enforces the safety
criterion. Hence, the overall path traced from the start state to the goal
state is safe.

Algorithm 2 RRT-KBF

$F,G,\psi_{max},a_{max},L,\gamma_{1},\gamma_{2}\leftarrow constants$

function RRT($start_{state},goal_{state},obst$)

$tree\leftarrow(null,start_{state},null)$

while $tree.visited(goal_{state})$ is $False$ do

$node_{v}\leftarrow\bf get\\_random\\_visited\\_sample\bf\text{($tree$)}$

$node_{n},u$ $\leftarrow\bf extend\\_sample\bf$($node_{v},obst$)

if $node_{n},u$ it not  $null$

$tree.add(node_{n},node_{r},u)$

end while

return $tree$

end function

function extend_sample($node_{n},obst$)

$u\leftarrow\bf get\\_uniform\\_sample()\bf$

if $\bf{check\\_collision\\_kbf\bf}(node_{n},u,obst)$

return $null,null$$\triangleright$ $u$ is non-optimal control

else

return $node_{r},u$$\triangleright$ $u$ is optimal control

end function

function check_collision_kbf($node,u,obst$)

$x_{p},y_{p}\leftarrow node.state$

$x_{o},y_{o},r_{o}\leftarrow obst.state$

$v_{x},v_{y}\leftarrow node.vel.x,node.vel.y$

$B\leftarrow({x_{p}}-{x_{o}})^{2}+({y_{p}}-{y_{o}})^{2}-r_{o}^{2}$

$\dot{B}\leftarrow 2(x_{p}-x_{o})v_{x}+2(y_{p}-y_{o})v_{y}$

${B_{1}}\leftarrow{\dot{B}}+{\gamma_{1}}{B}$

$\mu\leftarrow f(x)+g(x)u$

$\dot{B_{1}}\leftarrow\gamma_{1}\dot{B}+2v_{x}^{2}+2v_{y}^{2}+2\begin{bmatrix}x_{p}-x_{o}&y_{p}-y_{o}\end{bmatrix}\mu$

if $\dot{B_{1}}+\gamma_{2}B_{1}<0$

return $True$ $\triangleright$ CBF constraint fail

else

return $False$ $\triangleright$ CBF constraint pass

end function

###  III-B Robust RRT with Kinodynamic Barrier Function (Robust RRT-KBF)

Algorithm 3 Robust RRT-KBF

$F,G,\psi_{max},a_{max},L,\gamma_{1},\gamma_{2},\Delta_{1},\Delta_{2}\leftarrow
constants$

function check_collision_robust_kbf($node,u,obst$)

$x_{p},y_{p}\leftarrow node.state.pos$

$x_{o},y_{o}\leftarrow obst.state$

$v_{x},v_{y}\leftarrow node.state.vel.x,node.state.vel.y$

$B\leftarrow({x_{p}}-{x_{o}})^{2}+({y_{p}}-{y_{o}})^{2}-r^{2}$

$\dot{B}\leftarrow 2(x_{p}-x_{o})v_{x}+2(y_{p}-y_{o})v_{y}$

${B_{1}}\leftarrow{\dot{B}}+{\gamma_{1}}{B}$

$\mu\leftarrow F+Gu$

$\dot{B_{1}}\leftarrow\gamma_{1}\dot{B}+2v_{x}^{2}+2v_{y}^{2}+2\begin{bmatrix}x_{p}-x_{o}&y_{p}-y_{o}\end{bmatrix}\mu$

$A\leftarrow\gamma_{1}\dot{B_{1}}+2v_{x}^{2}+2v_{y}^{2}+\gamma_{2}B_{1}$

$b\leftarrow 2[x_{p}-x_{o}\;\;y_{p}-y_{o}]$

$\psi_{0}\leftarrow
max{((A+b*\Delta_{1}\textsuperscript{max}),(A-b*\Delta_{1}\textsuperscript{max}))}$

$\psi_{p}\leftarrow b*(1+\Delta_{2}\textsuperscript{max})$

$\psi_{n}\leftarrow b*(1-\Delta_{2}\textsuperscript{max})$

if $\psi_{0}+\psi_{p}*\mu\leq 0\text{ and }\psi_{0}-\psi_{n}*\mu\leq 0$

return $False$ $\triangleright$ Robust constraint pass

else

return $True$ $\triangleright$ Robust constraint fail

end function

The CBF equation (21) discussed in the previous section assumes that the true
dynamics of the system are known. To handle model uncertainties, QP
formulations of CBF were extended to yield the robust CBF constraints, as
introduced in [24]. We extend this work, deriving the robust CBF constraint
for the previously proposed RRT-KBF path planner, see Algorithm 3. To account
for the model uncertainties, we can use nominal dynamics model $\tilde{f}(x)$
and $\tilde{g}(x)$ in place of unknown true dynamics $f(x)$ and $g(x)$. Now,
equation (7) can be rewritten as:

$\tilde{u}=\tilde{g}(x)^{-1}(\mu-\tilde{f}(x))$ (24)

Substituting (24) into the dynamics equation (5) we get:

$\dot{x_{2}}=\mu+\Delta_{1}+\Delta_{2}\mu$ (25)

where

$\displaystyle\Delta_{1}=f(x)-g(x)\tilde{g}(x)^{-1}\tilde{f}(x)$ (26)
$\displaystyle\Delta_{2}=g(x)\tilde{g}(x)^{-1}-\mathrm{I}$ (27)

Here $\Delta_{1}$ and $\Delta_{2}$ represents the model uncertainty. Given
pseudo-control $\mu$, the CBF equation (21) can be expressed as:

$\dot{B_{1}}(x,\mu)=A(x)+b(x)\mu\geq 0$ (28)

where

$\displaystyle
A(x)=\gamma_{1}\dot{B}(x)+2v_{x}^{2}+2v_{y}^{2}+\gamma_{2}B_{1}(x)$ (29)
$\displaystyle b(x)=2\ [x_{p}-x_{o}\;\;y_{p}-y_{o}]$ (30)

Now equation (28) becomes:

$\dot{B_{1}}(x,\mu)=A(x)+b(x)(\mu+\Delta_{1}+\Delta_{2}\mu)\geq 0$ (31)

To minimize model uncertainties, we have to minimize equation (31).
Considering positive constants $\Delta_{1}^{max}$, $\Delta_{2}^{max}$ with
absolute values $|\Delta_{1}|\leq\Delta_{1}^{max}$ and
$|\Delta_{2}|\leq\Delta_{2}^{max}$, we can rewrite (31) as a maximization
problem:

$\displaystyle\dot{B_{1}}(x,\mu)=A(x)+b(x)(\mu+\Delta_{1}^{max}+\Delta_{2}^{max}\mu)$
(32) $\displaystyle\dot{B_{1}}(x,\mu)=\max(\psi_{0}+\psi_{1}\mu)\leq 0$ (33)

The maximum values for this function is given by:

$\displaystyle\psi_{0}^{max}=\max\begin{cases}A(x)+b(x)\Delta_{1}^{max}\\\
A(x)-b(x)\Delta_{1}^{max}\end{cases}$ (34)
$\displaystyle\psi_{1}^{p}=b(x)(1+\Delta_{2}^{max})$ (35)
$\displaystyle\psi_{1}^{n}=b(x)(1-\Delta_{2}^{max})$ (36)

Finally, we have the robust CBF constraints that has accounted for model
uncertainties:

$\displaystyle\psi_{0}^{max}+\psi_{1}^{p}\mu\leq 0$ (37)
$\displaystyle\psi_{0}^{max}+\psi_{1}^{n}\mu\leq 0$ (38)

To incorporate the robust CBF controller into our framework, we modify the
$\bf{check\\_collision\\_kbf\bf}$ in RRT-KBF algorithm to introduce robust
constraints (37) and (38) in the path planner.

##  IV NUMERICAL VALIDATION

To demonstrate the effectiveness of the proposed work, we design a two-stage
pipeline involving the path-planning phase followed by a path-following phase.
The path-planner (Algorithm 2, 3) generates a safety-critical reference path
$x_{rm}$ with the corresponding control $u_{ref}$. This information is used by
the path-follower with a feedback controller to generate a control that
guarantees stability and safety-critical constraints for the autonomous
vehicle. An overview of the simulation is presented as a block diagram in Fig.
1.

Figure 1: Block diagram of the proposed algorithm with application to
autonomous vehicles.

We conducted the numerical simulation on Cogniteam’s Hamster Robot [27]. The
Hamster V7 robot uses 2 Raspberry Pi modules (master-slave setup) and Arduino
Board as a low-level controller. This robot can move with a maximum velocity
of $1.2\text{\,}\mathrm{m}\mathrm{/}\mathrm{s}$ and can make maximum turns of
30∘ angle. We have abstracted obstacles as a circle for simplification. This
may be extended for other geometric shapes. The reader is encouraged to watch
the supplemental video111https://youtu.be/LtoM7CMWtp8 for visualizations of
our results.

$\begin{array}[]{cc}\includegraphics[width=91.0631pt]{images/RRT_U.png}&\includegraphics[width=91.0631pt]{images/U1.png}\\\
\mbox{(a1)}&\mbox{(b1)}\\\
\includegraphics[width=91.0631pt]{images/RRT_S.png}&\includegraphics[width=91.0631pt]{images/S1.png}\\\
\mbox{(a2)}&\mbox{(b2)}\\\
\includegraphics[width=91.0631pt]{images/RRT_C.png}&\includegraphics[width=91.0631pt]{images/C3.png}\\\
\mbox{(a3)}&\mbox{(b3)}\\\ \end{array}$

Figure 2: Comparative analysis: [a1 - a3] showcase the performance of RRT, [b1
- b3]: showcase the performance of RRT-KBF on different scenarios,
respectively

###  IV-A Path Planning

In the first phase, we run the path planner by providing the start, goal, and
obstacles information to Algorithm 2. The path planner returns the reference
model and the reference control as outputs. The path traced by different path
planners is shown in Fig. 2. There are several advantages of using the
proposed RRT-KBF planner over RRT:

  * •

The path provided by RRT-KBF is kinematically constrained.

  * •

The RRT-KBF algorithm also outputs the corresponding control that satisfies
safety conditions (21). The control can be directly applied to the robot to
take it from start to goal safely.

  * •

The RRT algorithm uses fixed step size for path planning, whereas RRT-KBF uses
dynamic steps based on the randomly sampled control.

###  IV-B Path Following

The outputs of the proposed path planners enforce only safety-critical
conditions (21). We need a feedback controller that satisfies the stability
constraints (17) running on the autonomous vehicle. The reference model and
control returned by the path planners are used by the CLF-CBF-QP controller
running on the Hamster robot to enforce stability constraints over the safety-
critical path. This ensures that the final path traced by the Hamster robot is
both stable and safe. Fig. 3 shows motion snapshots of the Hamster Robot using
our proposed approach in ROS/Gazebo simulation.

Figure 3: Snapshots of ROS simulation running RRT-KBF algorithm. Simulation video: https://youtu.be/LtoM7CMWtp8. TABLE I: Performance analysis of path planning algorithms | CONSTRAINTS | AVG. TIME (s) OVER 100 RUNS
---|---|---
| SAFETY | DYNAMIC | KINEMATIC | SCENARIO 1 | SCENARIO 2 | SCENARIO 3 | SCENARIO 4
RRT | YES | NO | NO | 0.71 | 0.77 | 0.73 | 0.77
RRT-CBF QP | YES | YES | NO | 9.37 | 11.72 | 9.42 | 11.14
RRT-KBF | YES | YES | YES | 1.11 | 1.12 | 1.16 | 1.18
TABLE II: Performance analysis with model uncertainty |  | AVG. TIME (s) OVER 100 RUNS
---
Robust RRT-KBF |  |  $\Delta_{1}^{max}$ = 0
---
$\Delta_{2}^{max}$ = 0
|  $\Delta_{1}^{max}$ = 0.3
---
$\Delta_{2}^{max}$ = 30
|  $\Delta_{1}^{max}$ = 0.5
---
$\Delta_{2}^{max}$ = 50
SCENARIO 1 | 1.11 | 1.12 | 3.06
SCENARIO 2 | 1.12 | 1.22 | 3.24
SCENARIO 3 | 1.16 | 1.10 | 3.38
SCENARIO 4 | 1.18 | 1.24 | 3.44

###  IV-C Robustness to Uncertainties

The Robust RRT-KBF uses the Robust CBF constraints (37, 38) in the path
planning framework to can handle model uncertainties. To evaluate the
performance of the algorithm under uncertainty, we introduce an error of 0.5m
in the position of the obstacles and an error of 0.25m in the size/radius of
the obstacle. Fig. 4 shows the effectiveness of Robust RRT-KBF
($\Delta_{1}^{max}=10$, $\Delta_{2}^{max}=0.1$) over RRT-KBF in both the
scenarios.

$\begin{array}[]{cc}\includegraphics[width=91.0631pt]{images/KBF_P.png}&\includegraphics[width=91.0631pt]{images/KBF_S.png}\\\
\mbox{(a1)}&\mbox{(a2)}\\\
\includegraphics[width=91.0631pt]{images/RKBF_P.png}&\includegraphics[width=91.0631pt]{images/RKBF_S.png}\\\
\mbox{(b1)}&\mbox{(b2)}\\\ \end{array}$

Figure 4: Comparative analysis: [a1 - a2] showcase the performance of RRT-KBF,
[b1 - b2] showcase the performance of Robust RRT-KBF with position and radius
uncertainties of 0.5m and 0.25m, respectively.

$\begin{array}[]{cc}\includegraphics[width=91.0631pt]{images/R_RRT_L.png}&\includegraphics[width=91.0631pt]{images/R_RRT_M.png}\\\
\mbox{(a) \small$\Delta_{1}^{max}=0.1,\Delta_{2}^{max}=10$}&\mbox{(b)
\small$\Delta_{1}^{max}=0.2,\Delta_{2}^{max}=20$}\\\
\includegraphics[width=91.0631pt]{images/R_RRT_MH.png}&\includegraphics[width=91.0631pt]{images/R_RRT_H.png}\\\
\mbox{(c) \small$\Delta_{1}^{max}=0.3,\Delta_{2}^{max}=30$}&\mbox{(d)
\small$\Delta_{1}^{max}=0.5,\Delta_{2}^{max}=50$}\\\ \end{array}$

Figure 5: Comparative analysis: [a - d] showcase the performance of Robust
RRT-KBF, with increasing uncertainties.

We can also control the degree of uncertainty in our simulation by setting
appropriate values for $\Delta_{1}^{max}$ and $\Delta_{2}^{max}$ (32). The
designed Robust RRT-KBF controller behaves as RRT-KBF controller on setting
uncertainty factor $\Delta_{1}^{max}=\Delta_{2}^{max}=0$. On increasing the
uncertainty i.e. $\Delta_{1}^{max}$ and $\Delta_{2}^{max}$, we can observe
that the path planner strictly avoids the obstacle cluster, see Fig. 5.

###  IV-D Performance Analysis

One of the primary focuses of this work is to ensure both path safety and
stability without introducing significant computation overhead on the existing
RRT-based path-planner. Table I shows the contrast between the RRT, RRT-CBF
QP, and the proposed RRT-KBF algorithm with an average run time of over 100
simulations in four different scenarios. While the RRT algorithm is the
fastest, it only enforces safety constraints. Using the QP-solver to
iteratively find the optimal path for dynamic robots proves to be a costlier
approach in terms of time complexity. The proposed RRT-KBF algorithm is able
to introduce safety, kinematic, and dynamic constraints on RRT with minimal
computational overhead. In comparison with [23], the use of random sampling in
place of QP-solver preserves the random nature of RRT and makes the algorithm
computationally efficient.

When we introduce model uncertainty into the planning framework, the
performance of the algorithm is directly dependent on the set of uncertainty
bounds, as seen in Table II. By setting $\Delta_{1}^{max}=\Delta_{2}^{max}=0$,
the Robust RRT-KBF effectively becomes RRT-KBF and gives the best run-time. On
increasing the uncertainty parameters $\Delta_{1}^{max},\Delta_{2}^{max}$, the
algorithm run-time increases significantly. Although the run-time of Robust
RRT-KBF is significantly higher under high uncertainty, this is faster when
compared to the traditional RRT-CBF QP.

##  V CONCLUSIONS

In this paper, we have presented a new technique for a safety-critical path
planner. The novelty of our solution unlike the conventional alternatives is
usage of Rapidly Exploring Random Trees (RRT) and Kinodynamic Barrier
Functions (KBF) for efficient planning. We also showcased robustness of RRT-
KBF in motion planning, and used the systemic nature and flexibility offered
by them to address uncertainties within the model. Further, we also
illustrated that by combining robust motion planning along with real-time
safety-critical control not only improves high-level planning but even real-
time collision avoidance for dynamic robotics.

## References

  * [1] Dijkstra, E. W., 1959.  “A note on two problems in connexion with graphs”.  Numerische mathematik,  1(1), pp. 269–271.
  * [2] Hart, P., Nilsson, N., and Raphael, B., 1968.  “A formal basis for the heuristic determination of minimum cost paths”.  IEEE Transactions on Systems Science and Cybernetics,  4(2), pp. 100–107.
  * [3] Bruce, J., and Veloso, M., 2002.  “Real-time randomized path planning for robot navigation”.  In IEEE/RSJ International Conference on Intelligent Robots and Systems, Vol. 3, pp. 2383–2388 vol.3.
  * [4] Stentz, A., 1993.  “Optimal and efficient path planning for unknown and dynamic environments”.  INTERNATIONAL JOURNAL OF ROBOTICS AND AUTOMATION,  10, pp. 89–100.
  * [5] Stentz, A., 1995.  “The focussed d* algorithm for real-time replanning”.  In In Proceedings of the International Joint Conference on Artificial Intelligence, pp. 1652–1659.
  * [6] Koenig, S., and Likhachev, M., 2005.  “Fast replanning for navigation in unknown terrain”.  IEEE Transactions on Robotics,  21(3), pp. 354–363.
  * [7] Likhachev, M., Ferguson, D., Gordon, G., Stentz, A., and Thrun, S., 2005.  “Anytime dynamic a*: An anytime, replanning algorithm”.  In Proceedings of the Fifteenth International Conference on International Conference on Automated Planning and Scheduling, ICAPS’05, AAAI Press, p. 262–271.
  * [8] Hwang, Y. K., and Ahuja, N., 1992.  “A potential field approach to path planning”.  IEEE Transactions on Robotics and Automation,  8(1), pp. 23–32.
  * [9] Koren, Y., Borenstein, J., et al.  “Potential field methods and their inherent limitations for mobile robot navigation.”.
  * [10] Faria, G., Romero, R. A. F., Prestes, E., and Idiart, M. A. P., 2004.  “Comparing harmonic functions and potential fields in the trajectory control of mobile robots”.  In IEEE Conference on Robotics, Automation and Mechatronics, 2004., Vol. 2, pp. 762–767 vol.2.
  * [11] Karaman, S., Walter, M. R., Perez, A., Frazzoli, E., and Teller, S., 2011.  “Anytime motion planning using the rrt”.  In 2011 IEEE International Conference on Robotics and Automation, IEEE, pp. 1478–1483.
  * [12] Nasir, J., Islam, F., Malik, U., Ayaz, Y., Hasan, O., Khan, M., and Muhammad, M. S., 2013.  “Rrt*-smart: A rapid convergence implementation of rrt”.  International Journal of Advanced Robotic Systems,  10(7), p. 299.
  * [13] Berenson, D., Srinivasa, S. S., Ferguson, D., and Kuffner, J. J., 2009.  “Manipulation planning on constraint manifolds”.  In 2009 IEEE international conference on robotics and automation, IEEE, pp. 625–632.
  * [14] Yavari, M., Gupta, K., and Mehrandezh, M., 2019.  “Lazy steering rrt*: An optimal constrained kinodynamic neural network based planner with no in-exploration steering”.  In 2019 19th International Conference on Advanced Robotics (ICAR), pp. 400–407.
  * [15] Kavraki, L. E., Svestka, P., Latombe, J. ., and Overmars, M. H., 1996.  “Probabilistic roadmaps for path planning in high-dimensional configuration spaces”.  IEEE Transactions on Robotics and Automation,  12(4), pp. 566–580.
  * [16] Arslan, O., and Tsiotras, P., 2015.  “Machine learning guided exploration for sampling-based motion planning algorithms”.  In 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 2646–2652.
  * [17] Saska, M., Macas, M., Preucil, L., and Lhotska, L., 2006.  “Robot path planning using particle swarm optimization of ferguson splines”.  In 2006 IEEE Conference on Emerging Technologies and Factory Automation, pp. 833–839.
  * [18] Ames, A. D., Coogan, S., Egerstedt, M., Notomista, G., Sreenath, K., and Tabuada, P., 2019.  “Control barrier functions: Theory and applications”.  In 2019 18th European Control Conference (ECC), pp. 3420–3431.
  * [19] Ames, A. D., Grizzle, J. W., and Tabuada, P., 2014.  “Control barrier function based quadratic programs with application to adaptive cruise control”.  In 53rd IEEE Conference on Decision and Control, pp. 6271–6278.
  * [20] Son, T. D., and Nguyen, Q., 2019.  “Safety-critical control for non-affine nonlinear systems with application on autonomous vehicle”.  In 2019 IEEE 58th Conference on Decision and Control (CDC), IEEE, pp. 7623–7628.
  * [21] Hsu, S., Xu, X., and Ames, A. D., 2015.  “Control barrier function based quadratic programs with application to bipedal robotic walking”.  In 2015 American Control Conference (ACC), pp. 4542–4548.
  * [22] Nguyen, Q., Da, X., Grizzle, J., and Sreenath, K., 2020.  “Dynamic walking on stepping stones with gait library and control barrier functions”.  In Algorithmic Foundations of Robotics XII. Springer, pp. 384–399.
  * [23] Yang, G., Vang, B., Serlin, Z., Belta, C., and Tron, R., 2019.  “Sampling-based motion planning via control barrier functions”.  In Proceedings of the 2019 3rd International Conference on Automation, Control and Robots, ICACR 2019, Association for Computing Machinery, p. 22–29.
  * [24] Nguyen, Q., and Sreenath, K., 2016.  “Optimal robust control for constrained nonlinear hybrid systems with application to bipedal locomotion”.  In 2016 American Control Conference (ACC), pp. 4807–4813.
  * [25] Ames, A. D., Galloway, K., Sreenath, K., and Grizzle, J. W., 2014.  “Rapidly exponentially stabilizing control lyapunov functions and hybrid zero dynamics”.  IEEE Transactions on Automatic Control,  59(4), pp. 876–891.
  * [26] Nguyen, Q., and Sreenath, K., 2016.  “Exponential control barrier functions for enforcing high relative-degree safety-critical constraints”.  In 2016 American Control Conference (ACC), pp. 322–328.
  * [27] Hamster v7.  https://www.hamster-robot.com/.  Accessed: 2021-02-25.


††thanks: These authors contributed equally††thanks: These authors contributed
equally††thanks: These authors contributed equally

# Experimental Simulation of Larger Quantum Circuits with Fewer
Superconducting Qubits

Chong Ying  Hefei National Research Center for Physical Sciences at the
Microscale and School of Physical Sciences, University of Science and
Technology of China, Hefei 230026, China  Shanghai Research Center for Quantum
Science and CAS Center for Excellence in Quantum Information and Quantum
Physics, University of Science and Technology of China, Shanghai 201315, China
Hefei National Laboratory, University of Science and Technology of China,
Hefei 230088, China  Bin Cheng  Centre for Quantum Software and Information,
Faculty of Engineering and Information Technology, University of Technology
Sydney, NSW 2007, Australia.  Department of Physics, Southern University of
Science and Technology, Shenzhen 518055, China.  Shenzhen Institute for
Quantum Science and Engineering, Southern University of Science and
Technology, Shenzhen 518055, China.  Youwei Zhao  Hefei National Research
Center for Physical Sciences at the Microscale and School of Physical
Sciences, University of Science and Technology of China, Hefei 230026, China
Shanghai Research Center for Quantum Science and CAS Center for Excellence in
Quantum Information and Quantum Physics, University of Science and Technology
of China, Shanghai 201315, China  Hefei National Laboratory, University of
Science and Technology of China, Hefei 230088, China  He-Liang Huang
<EMAIL_ADDRESS>Hefei National Research Center for Physical Sciences at
the Microscale and School of Physical Sciences, University of Science and
Technology of China, Hefei 230026, China  Shanghai Research Center for Quantum
Science and CAS Center for Excellence in Quantum Information and Quantum
Physics, University of Science and Technology of China, Shanghai 201315, China
Hefei National Laboratory, University of Science and Technology of China,
Hefei 230088, China  Henan Key Laboratory of Quantum Information and
Cryptography, Zhengzhou, Henan 450000, China  Yu-Ning Zhang  Department of
Physics, Southern University of Science and Technology, Shenzhen 518055,
China.  Shenzhen Institute for Quantum Science and Engineering, Southern
University of Science and Technology, Shenzhen 518055, China.  QuTech, Delft
University of Technology, P.O. Box 5046, 2600 GA Delft, The Netherlands.  Ming
Gong<EMAIL_ADDRESS>Yulin Wu  Hefei National Research Center for
Physical Sciences at the Microscale and School of Physical Sciences,
University of Science and Technology of China, Hefei 230026, China  Shanghai
Research Center for Quantum Science and CAS Center for Excellence in Quantum
Information and Quantum Physics, University of Science and Technology of
China, Shanghai 201315, China  Hefei National Laboratory, University of
Science and Technology of China, Hefei 230088, China  Shiyu Wang  Futian Liang
Jin Lin  Yu Xu  Hefei National Research Center for Physical Sciences at the
Microscale and School of Physical Sciences, University of Science and
Technology of China, Hefei 230026, China  Shanghai Research Center for Quantum
Science and CAS Center for Excellence in Quantum Information and Quantum
Physics, University of Science and Technology of China, Shanghai 201315, China
Hefei National Laboratory, University of Science and Technology of China,
Hefei 230088, China  Hui Deng  Hao Rong  Cheng-Zhi Peng  Hefei National
Research Center for Physical Sciences at the Microscale and School of Physical
Sciences, University of Science and Technology of China, Hefei 230026, China
Shanghai Research Center for Quantum Science and CAS Center for Excellence in
Quantum Information and Quantum Physics, University of Science and Technology
of China, Shanghai 201315, China  Hefei National Laboratory, University of
Science and Technology of China, Hefei 230088, China  Man-Hong Yung
<EMAIL_ADDRESS>Department of Physics, Southern University of Science and
Technology, Shenzhen 518055, China.  Shenzhen Institute for Quantum Science
and Engineering, Southern University of Science and Technology, Shenzhen
518055, China.  Guangdong Provincial Key Laboratory of Quantum Science and
Engineering, Southern University of Science and Technology, Shenzhen 518055,
China.  Shenzhen Key Laboratory of Quantum Science and Engineering, Southern
University of Science and Technology, Shenzhen, 518055, China.  Xiaobo Zhu
Jian-Wei Pan  Hefei National Research Center for Physical Sciences at the
Microscale and School of Physical Sciences, University of Science and
Technology of China, Hefei 230026, China  Shanghai Research Center for Quantum
Science and CAS Center for Excellence in Quantum Information and Quantum
Physics, University of Science and Technology of China, Shanghai 201315, China
Hefei National Laboratory, University of Science and Technology of China,
Hefei 230088, China

###### Abstract

Although near-term quantum computing devices are still limited by the quantity
and quality of qubits in the so-called NISQ era, quantum computational
advantage has been experimentally demonstrated. Moreover, hybrid architectures
of quantum and classical computing have become the main paradigm for
exhibiting NISQ applications, where low-depth quantum circuits are repeatedly
applied. In order to further scale up the problem size solvable by the NISQ
devices, it is also possible to reduce the number of physical qubits by
“cutting” the quantum circuit into different pieces. In this work, we
experimentally demonstrated a circuit-cutting method for simulating quantum
circuits involving many logical qubits, using only a few physical
superconducting qubits. By exploiting the symmetry of linear-cluster states,
we can estimate the effectiveness of circuit-cutting for simulating up to
33-qubit linear-cluster states, using at most 4 physical qubits for each
subcircuit. Specifically, for the 12-qubit linear-cluster state, we found that
the experimental fidelity bound can reach as much as 0.734, which is about 19%
higher than a direct simulation on the same 12-qubit superconducting
processor. Our results indicate that circuit-cutting represents a feasible
approach of simulating quantum circuits using much fewer qubits, while
achieving a much higher circuit fidelity.

Introduction.— Quantum computing offers potential speedups over classical
computing on many applications, such as factoring [1, 2, 3], unstructured
search [4] and quantum simulation [5, 6, 7] . However, these applications
require quantum computers to be fault-tolerant, which is still out of reach of
the current quantum technology. Instead, we have just entered the noisy
intermediate-scale quantum (NISQ) era [8, 9], meaning that the number of
physical qubits are sizable in terms of the computational space, but they are
error-prone or noisy. Recent experimental demonstrations of quantum
computation involves about 50 to 60 qubits [10, 11, 12]. Although in terms of
the memory size, they might have already exceeded the limits of classical
super-computers, the incorrectable noisy gates limits the depth of quantum
circuits running on current quantum devices, which constitutes a major
obstacle to finding practical applications. Therefore, it is of practical
interest to solve large problems with smaller quantum devices, even with a
tradeoff of using more classical resources.

This topic can be roughly categorized into two branches; one is at the
algorithmic level, and the other is at the circuit level. The former is to
decompose a large problem into smaller subproblems, each of which is solved by
a small quantum computer. Examples include quantizing classical divide-and-
conquer algorithms to solve combinatorial optimization problems [13, 14], and
Fujii $et~{}al$’s deep variational quantum eigensolver framework [15], which
is suitable for simulating physical systems when interactions between
subsystems are weak. Partially quantizing a tensor network may also fall into
this category [16, 17].

Figure 1: (a) Example illustrating the circuit cutting scheme. The quantum
circuit on the left-hand side is cut at the red cross, and partitioned into
two subcircuits. The original circuit can be simulated by combining the
quantum measurement statistics of two subcircuits in different basis and of
different inputd. (b) The list of $c_{i},O_{i}$ and $\rho_{i}$ for Eq. (2).
(c) Left. A 12-qubit linear-cluster state. Right. The 12-qubit linear-cluster
state can be simulated by combining measurement data from these two
subcircuits.

The circuit-level schemes intends to decompose a large quantum circuit into
smaller pieces, implement each piece independently and finally use classical
computers to combine to results. For example, Bravyi $et~{}al.$ [18] discussed
methods of using classical postprocessing to add virtual qubits for sparse
circuits and Pauli-based computation. Mitarai and Fujii [19] proposed a method
to add virtual two-qubit gates, which means that a remote two-qubit gate can
be simulated by a quasiprobability decomposition of local single-qubit gates,
thus cutting the large quantum circuit. Their work is for general quantum
circuits and has been extended in a recent work [20] to allow decomposing non-
local quantum channels into local ones. On the other hand, using the language
of tensor network, Peng $et$ $al.$ [21] proposed a tomography-like circuit-
cutting scheme, which is endowed with a rigorous analysis of the required
quantum and classical resources to simulate general quantum circuits. The
circuit-cutting scheme is further analyzed and improved in later works [22,
23, 24, 25].

In this work, we experimentally implement a tomography-like circuit-cutting
scheme to simulate large linear-cluster states. Due to the symmetry in linear-
cluster states, we only need to run subcircuits with at most 4 superconducting
qubits and the simulated linear-cluster states scale up to 33 qubits. To
analyze the performance, we use the stabilizer technique [26, 27] to estimate
the fidelity lower bound. Then, it is compared with the fidelity bound
obtained in a previous work that prepared the 12-qubit state directly [28].
The circuit-cutting scheme achieves a fidelity bound 0.734 in the 12-qubit
case, which is about 19% higher than the previous experiment. Our experimental
result shows the promise that the circuit-cutting scheme might become a
standard tool in NISQ applications.

Cutting large quantum circuits.— The basic idea is to cut a qubit wire and
then simulate the propagation of quantum information by classically combining
the quantum measurement data. We illustrate this with an example in Fig. 1
(a). First, observe that at the time slice of the cutting point (the red
cross), the reduced density matrix of the first two qubits can be decomposed
as,

$\displaystyle\rho^{ab}=\frac{1}{2}\sum_{j=0}^{3}\Tr_{b}(\rho^{ab}\sigma_{j}^{b})\otimes\sigma_{j}^{b}\
.$ (1)

where we use superscripts to explicitly indicate the qubit labels and
$\sigma_{j}\in\\{I,X,Y,Z\\}$. Each Pauli operator can be further decomposed
into its eigenstates, e.g., $Z=\outerproduct{0}{0}-\outerproduct{1}{1}$. Note
that the identity operator can be written as
$I=\outerproduct{0}{0}+\outerproduct{1}{1}$, which can be combined with $Z$;
such reuse of eigenstates was mentioned in Ref. [22]. Then, after combining
the expansion of $I$ and $Z$, we have,

$\displaystyle\rho^{ab}=\sum_{i=1}^{6}c_{i}\Tr_{b}(\rho^{ab}O^{b}_{i})\otimes\rho^{b}_{i}\
,$ (2)

where the $c_{i},O_{i},\rho_{i}$ are listed in Fig. 1 (b). At this point, the
physical meaning of the above formula becomes clear. To simulate the original
circuit, we first cut it into two subcircuits. The partial trace operation in
Eq. (2) can be interpreted as measuring $O_{i}$ in the qubit $b$ of subcircuit
1, and then $\rho_{i}$ is prepared and passed as input to subcircuit 2. In
this way, the original circuit is cut into two independent subcircuits, and
later operations in qubit $a$ will not affect the quantum state of subcircuit
2. This measure-and-prepare process is performed for each $O_{i}$ and
$\rho_{i}$, and then combining the measurement data from two subcircuits with
coefficients $c_{i}$ recovers the corresponding measurement data of the
original circuit. We remark that the combination of quantum statistics is
achieved with classical computer. Note that this illustration is essentially
the same as Ref. [21], except that they use the language of tensor network,
and a total of 8 terms appear in their decomposition (see Lemma 1 therein).

For more general and larger quantum circuits, one can apply this cutting
scheme iteratively to several cutting points, to partition the whole circuit
into several disconnected pieces of subcircuits. By running the subcircuits
independently, and classically combining the measurement statistics with
appropriate coefficients, one obtains expectations of the large quantum
circuits. The quantum running time is exponential on the number of cutting
points.

Linear-cluster states.— Cluster states are a family of highly-entangled
states, which can be used to achieve measurement-based quantum computation
[29, 30]. That is, universal quantum computation can be performed by only
making measurements on the cluster state. Linear-cluster state is a specific
example of cluster states, where all qubits are aligned in one dimension.
Explicitly, a linear-cluster state with $n$ qubits can be expressed as,

$\displaystyle\ket{\mathsf{LC}_{n}}=\left(\prod_{i=1}^{n-1}\mathrm{CZ}^{i,i+1}\right)\ket{+}^{\otimes
n}\ ,$ (3)

where the superscripts in the CZ gates indicate the qubits that they act on.

In this work, we experimentally simulate a 12-qubit linear-cluster state, with
4 qubits of a superconducting quantum processor, which is the same processor
as in Ref. [28]. As in Fig 1 (c), there are 3 cutting points in the 12-qubit
circuit, partitioning it into 4 subcircuits. The first 3 subcircuits are all
in the form of subcircuit 1, while the last subcircuit is in the form of
subcircuit 2. This is due to the symmetry of linear-cluster states. Note that
with the same subcircuits, we can simulate 15-qubit and larger circuits. All
we have to do is to repeat measurement data from subcircuit 1 in the classical
postprocessing, and there is no overhead in quantum resources.

To compare the performance of the circuit cutting scheme with that of running
the 12-qubit circuit directly, we need to estimate their fidelities. We follow
the approach in Ref. [28], which uses techniques from entanglement detection
in the stabilizer formalism [26, 27]. Let $s_{1}=X_{1}Z_{2}$,
$s_{n}=Z_{n-1}X_{n}$ and $s_{i}=Z_{i-1}X_{i}Z_{i+1}$ for $i\neq 1$ or $n$,
which commute with each other. It can be shown that a linear-cluster state is
a stabilizer state with a stabilizer group spanned by
$\\{s_{1},\cdots,s_{n}\\}$, i.e.,
$s_{i}\ket{\mathsf{LC}_{n}}=\ket{\mathsf{LC}_{n}}$ for $i=1,\cdots,n$. Let

$\displaystyle\mathsf{ODD}$ $\displaystyle:=\prod_{i\text{
odd}}\frac{1+s_{i}}{2}$ $\displaystyle\mathsf{EVEN}$
$\displaystyle:=\prod_{i\text{ even}}\frac{1+s_{i}}{2}\ .$ (4)

For a linear-cluster state, one has
$\outerproduct{\mathsf{LC}_{n}}{\mathsf{LC}_{n}}\geq\mathsf{ODD}+\mathsf{EVEN}-I$
[26, Theorem 6]. That means, for an unknown quantum state $\rho$, its fidelity
relative to the linear-cluster state is lower bounded by,

$\displaystyle\Tr(\rho\outerproduct{\mathsf{LC}_{n}}{\mathsf{LC}_{n}})\geq\Tr(\rho\mathsf{ODD})+\Tr(\rho\mathsf{EVEN})-1\
.$ (5)

Therefore, one can estimate the fidelity by measuring the operators
$\mathsf{ODD}$ and $\mathsf{EVEN}$. Observe that every term in the expansion
of $\mathsf{ODD}$ can be measured by making measurement in the basis
$XZXZ\cdots$, while every term in the expansion of $\mathsf{EVEN}$ can be
measured by making measurement in the basis $ZXZX\cdots$. Therefore, to
estimate the fidelity, one only needs to perform measurements in two bases.
For simplicity, we will refer to them as $XZ$ measurement and $ZX$
measurement, respectively.

Figure 2: (a) Processor structure diagram, we choose the qubits of Q3 to Q6
for the 4-qubit subcircuits, and Q4 to Q6 for the 3-qubit subcircuits. (b) 36
waveforms for 4-qubit subcircuits. The gray box shows the 6 initial state
preparation waveforms, in which three different virtual Z [9] are used. The
red box shows the measurement bases waveforms of $XZX$ and $ZXZ$ for the first
three qubits, and the orange box shows the measurement bases waveforms of
$X$,$Y$,$Z$ for the fourth qubit. (c) 12 waveforms for 3-qubit subcircuits,
with 6 initial state preparation waveforms in the gray box, and $XZX$ and
$ZXZ$ measurements waveforms in the red box.

Experiment.— To verify the the feasibility and evaluate the actual performance
of the scheme in the experiment, we run the subcircuits in Fig. 1 on a
12-qubit superconducting quantum processor. As shown in Fig. 2 (a), the qubits
are arranged in a one-dimensional chain. Each qubit has two control lines to
provide full control of the qubit: a microwave $XY$ control line to drive
excitations between $|0\rangle$ and $|1\rangle$, and a magnetic flux bias line
to tune the qubit resonance frequency. As the near-neighbor qubits are
capacitively coupled, the fast adiabatic CZ gates [31, 32] can be applied. The
measurements of qubit are done through dispersively coupling to a readout
resonator. We choose four adjacent qubits from a 12-qubit superconducting
quantum processor to implement the experiments. The average performance of the
chosen qubits are: $T_{1}\approx$ 36.1 $\mu$s, $T_{2}^{*}\approx$ 4.3 $\mu$s,
single-qubit gate fidelity $\approx$ 99.93% and CZ gate fidelity $\approx$
98.5%. More detailed data is shown in Table. S1.

For the 4-qubit subcircuits, we prepare 6 initial states with 6 different
waveforms and measure the first three qubits in both $XZX$ and $ZXZ$ basis,
while the fourth qubit is measured in three different bases $X$,$Y$,$Z$, thus
running a total of 36 circuits (The waveforms of the circuits are shown in
Fig. 2 (b)). For the 3-qubit subcircuits (see Fig. 2 (c)), we prepared 6
initial states by 6 different waveforms and measured the three qubits in both
$XZX$ and $ZXZ$ basis, thus running a total of 12 circuits.

Figure 3: (a) The output distributions from $XZ$ measurement of the 4-qubit
and 3-qubit linear cluster states. (b) Expectations from $XZ$ and $ZX$
measurements of the 4-qubit and 3-qubit linear cluster states. Ideal values
are one. The error bars are due to the repeated experiments.

For each subcircuit, we perform 1,000,000 shots of measurement. All the
experimental results are processed using the transition matrix error
mitigation (TMEM) method [33, 34], to suppress the readout noise. However,
negative entries may appear in the probability distributions of the
subcircuits after the TMEM. To make these distributions physical, we first
transform those probability distributions into diagonal operators, and then
use the maximum likelihood method to find a density operator that are the
closest to them [35, 36]. The final distributions of the subcircuits are then
extracted from these density operators. Before and after the experiment for
the purpose of cutting large circuits, additional quantum state tomography on
the final state of the circuit are performed to evaluate the performance of
the experiments. The average fidelity of the final states of the 4-qubit
subcircuit is 0.944, and the average fidelity of the final states of the
3-qubit subcircuit is 0.955, showing the high quality of the experiments.

Figure 4: (a) Comparison of the expectations with $XZ$ measurement obtained
from the 12-qubit circuit [28] (orange) and from the circuit-cutting scheme by
running smaller quantum circuits (blue). Each bar corresponds to one specific
observable in $\mathsf{ODD}$ and there are 64 expectations for each group. The
ideal values of all these expectations are one. (b) Fidelity bound (blue) and
processing time (red) for simulating large linear-cluster state using the same
experimental data from the 4-qubit and 3-qubit circuits. The circuit-cutting
experiments are repeated 25 times, and the error bars in both subfigures
indicate the fluctuation due to repeated experiments.

To estimate the fidelity of the large quantum circuit reconstructed by small
subcircuits, we need to compute $\Tr(\rho\mathsf{ODD})$ and
$\Tr(\rho\mathsf{EVEN})$. That is, we calculate the expectations of the terms
in their expansion (Eq. (4)), and then take the average. Note that any terms
in the expansion of $\mathsf{ODD}$ and $\mathsf{EVEN}$ are stabilizers of
$\ket{\mathsf{LC}_{n}}$, meaning that they all have expectations 1 with
respect to $\ket{\mathsf{LC}_{n}}$, in the absence of noise. Note that for the
subcircuits, if we take $\ket{\psi_{i}}=\ket{+}$, then they correspond to a
4-qubit and 3-qubit linear-cluster state, respectively. The corresponding
probability distributions from the $XZ$ measurement are shown in Fig. 3 (a),
which also includes the theoretical distributions for a comparison. Here, each
cell represents one bit string, and its color indicates the probability. There
are $2^{4}$ cells for the 4-qubit distributions and $2^{3}$ cells for the
3-qubit distributions. The probability distributions from $ZX$ measurement can
be found in Supplemental Materials. Then, in Fig. 3 (b), the expectations of
the terms in the expansion of both $\mathsf{ODD}$ and $\mathsf{EVEN}$ are
presented. From these expectations, we derive the fidelity lower bound for the
4-qubit linear-cluster state is 0.713, while that for the 3-qubit linear-
cluster state is 0.909. These bounds match the average fidelity from quantum
state tomography.

With the measurement data from the subcircuits, one can simulate larger
linear-cluster states, and the fidelity bounds can be derived with similar
procedures. Fig. 4 (a) presents the expectations of terms in $\mathsf{ODD}$
for the 12-qubit state obtained by the circuit-cutting scheme and a direct
simulation. Those expectations correspond to the $XZ$ measurement and there
are $2^{6}=64$ expectations in total. The blue bars are reconstructed from the
circuit-cutting scheme, while the orange bars are from the experimental data
in Ref. [28]. Each bar corresponds to one specific terms in the expansion of
$\mathsf{ODD}$ and the ideal value is one. The concrete values of each
expectation as well as those with the $ZX$ measurement are public-available
[37]. We remark that the distributions from the 12-qubit experiment are also
processed with the same procedure (the fidelity bound after processing is
0.615), i.e., TMEM followed by a maximum likelihood method, for a fair
comparison. From these expectations, we can similarly use Eq. (5) to estimate
the fidelity. The estimated fidelity bound from the circuit-cutting scheme is
0.734, about 19% higher than that from the experiment of Ref. [28]. Moreover,
as we mentioned before, the same measurement data can be used to simulate
larger linear-cluster states by exploiting symmetry, at a cost of increasing
overhead in classical postprocessing. Specifically, using the 3-qubit and
4-qubit subcircuits, one can simulate linear-cluster states of size $6+3k$,
where $k$ is a positive integer. But the obtained fidelity bound is expected
to decay as the number of qubits increases, since the error accumulates in the
classical postprocessing. The fidelity decay and classical postprocessing time
are shown in Fig. 4 (b).

Discussion.— In this work, we experimentally demonstrate a circuit-cutting
scheme and simulate larger linear-cluster state with size scaling up to 33
qubits, using at most 4 qubits. In the case of 12 qubits, we achieve a higher
fidelity compared to that of a previous work that prepared the 12-qubit state
directly [28], giving supporting evidence to the applicability of the circuit-
cutting scheme.

Simulating large quantum circuits with small quantum devices is a promising
direction in the NISQ era. Currently, there exist several circuit-cutting
schemes [18, 21, 19, 20]; it is necessary to further perform experimental
benchmarking on these schemes, in order to evaluate their applicability in
practice. On the other hand, although circuit-cutting schemes provide
systematic methods to cutting quantum circuits into smaller pieces, to the
best of our knowledge, there is no general method for determining the optimal
cutting points. Therefore, we believe that the potential of circuit-cutting
has not yet been fully explored.

Acknowledgement.— The authors thank the Laboratory of Microfabrication,
University of Science and Technology of China, Institute of Physics CAS, and
National Center for Nanoscience and Technology for supporting the sample
fabrication. The authors also thank QuantumCTek Co., Ltd., for supporting the
fabrication and the maintenance of room-temperature electronics. BC thanks the
support from the Sydney Quantum Academy, Sydney, NSW, Australia. Funding: This
research was supported by Innovation Program for Quantum Science and
Technology (Grant No. 2021ZD0300200), NSFC (Grants No. 11574380, No.
11905217), the Chinese Academy of Science and its Strategic Priority Research
Program (Grants No. XDB28000000), Shanghai Municipal Science and Technology
Major Project (Grant No.2019SHZDZX01), the Science and Technology Committee of
Shanghai Municipality, Anhui Initiative in Quantum Information Technologies,
and Special funds from Jinan science and Technology Bureau and Jinan high tech
Zone Management Committee. MHY is supported by the National Natural Science
Foundation of China (11875160), the Guangdong Innovative and Entrepreneurial
Research Team Program (2016ZT06D348), Natural Science Foundation of Guangdong
Province (2017B030308003), and Science, Technology and Innovation Commission
of Shenzhen Municipality (ZDSYS20170303165926217, JCYJ20170412152620376,
JCYJ20170817105046702). H.-L. H. acknowledges support from the Youth Talent
Lifting Project (Grant No. 2020-JCJQ-QT-030), National Natural Science
Foundation of China (Grants No. 11905294), China Postdoctoral Science
Foundation, and the Open Research Fund from State Key Laboratory of High
Performance Computing of China (Grant No. 201901-01).

## References and Notes

  * [1] P. Shor, Algorithms for quantum computation: discrete logarithms and factoring, in  _Proceedings 35th Annual Symposium on Foundations of Computer Science_ (IEEE Comput. Soc. Press).
  * Lu  _et al._ [2007] C.-Y. Lu, D. E. Browne, T. Yang, and J.-W. Pan, Demonstration of a compiled version of shor’s quantum factoring algorithm using photonic qubits, Phys. Rev. Lett. 99, 250504 (2007).
  * Huang  _et al._ [2017] H.-L. Huang, Q. Zhao, X. Ma, C. Liu, Z.-E. Su, X.-L. Wang, L. Li, N.-L. Liu, B. C. Sanders, C.-Y. Lu, and J.-W. Pan, Experimental blind quantum computing for a classical client, Phys. Rev. Lett. 119, 050503 (2017).
  * Grover [1996] L. K. Grover, A fast quantum mechanical algorithm for database search, in  _Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing_, STOC ’96 (Association for Computing Machinery, New York, NY, USA, 1996) p. 212–219.
  * Feynman [1982] R. P. Feynman, Simulating physics with computers, Int. J. Theor. Phys. 21, 467 (1982).
  * Lloyd [1996] S. Lloyd, Universal quantum simulators, Science 273, 1073 (1996).
  * Huang  _et al._ [2021] H.-L. Huang, M. Narożniak, F. Liang, Y. Zhao, A. D. Castellano, M. Gong, Y. Wu, S. Wang, J. Lin, Y. Xu, H. Deng, H. Rong, J. P. Dowling, C.-Z. Peng, T. Byrnes, X. Zhu, and J.-W. Pan, Emulating quantum teleportation of a majorana zero mode qubit, Phys. Rev. Lett. 126, 090502 (2021).
  * Preskill [2018] J. Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2, 79 (2018).
  * Huang  _et al._ [2020] H.-L. Huang, D. Wu, D. Fan, and X. Zhu, Superconducting quantum computing: a review, Sci. China Inf. Sci. 63, 180501 (2020).
  * Arute  _et al._ [2019] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, Quantum supremacy using a programmable superconducting processor, Nature 574, 505 (2019).
  * Wu  _et al._ [2021] Y. Wu, W.-S. Bao, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y. Du, D. Fan, M. Gong, C. Guo, C. Guo, S. Guo, L. Han, L. Hong, H.-L. Huang, Y.-H. Huo, L. Li, N. Li, S. Li, Y. Li, F. Liang, C. Lin, J. Lin, H. Qian, D. Qiao, H. Rong, H. Su, L. Sun, L. Wang, S. Wang, D. Wu, Y. Xu, K. Yan, W. Yang, Y. Yang, Y. Ye, J. Yin, C. Ying, J. Yu, C. Zha, C. Zhang, H. Zhang, K. Zhang, Y. Zhang, H. Zhao, Y. Zhao, L. Zhou, Q. Zhu, C.-Y. Lu, C.-Z. Peng, X. Zhu, and J.-W. Pan, Strong quantum computational advantage using a superconducting quantum processor, Phys. Rev. Lett. 127, 180501 (2021).
  * Zhu  _et al._ [2022] Q. Zhu, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y. Du, D. Fan, M. Gong, _et al._ , Quantum computational advantage via 60-qubit 24-cycle random circuit sampling, Sci. Bull. 67, 240 (2022).
  * Dunjko  _et al._ [2018] V. Dunjko, Y. Ge, and J. I. Cirac, Computational speedups using small quantum devices, Phys. Rev. Lett. 121, 250501 (2018).
  * Ge and Dunjko [2020] Y. Ge and V. Dunjko, A hybrid algorithm framework for small quantum computers with application to finding hamiltonian cycles, J. Math. Phys. 61, 012201 (2020).
  * Fujii  _et al._ [2022] K. Fujii, K. Mizuta, H. Ueda, K. Mitarai, W. Mizukami, and Y. O. Nakagawa, Deep variational quantum eigensolver: A divide-and-conquer method for solving a larger problem with smaller size quantum computers, PRX Quantum 3, 010346 (2022).
  * Liu  _et al._ [2019] J.-G. Liu, Y.-H. Zhang, Y. Wan, and L. Wang, Variational quantum eigensolver with fewer qubits, Phys. Rev. Research 1, 023025 (2019).
  * Yuan  _et al._ [2021] X. Yuan, J. Sun, J. Liu, Q. Zhao, and Y. Zhou, Quantum simulation with hybrid tensor networks, Phys. Rev. Lett. 127, 040501 (2021).
  * Bravyi  _et al._ [2016] S. Bravyi, G. Smith, and J. A. Smolin, Trading Classical and Quantum Computational Resources, Phys. Rev. X 6, 021043 (2016).
  * Mitarai and Fujii [2021] K. Mitarai and K. Fujii, Constructing a virtual two-qubit gate by sampling single-qubit operations, New J. Phys. 23, 023021 (2021).
  * Mitarai and Fujii [2020] K. Mitarai and K. Fujii, Overhead of the non-local-to-local channel decomposition by quasiprobability sampling, arXiv:2006.11174 , 7 (2020), arXiv:2006.11174.
  * Peng  _et al._ [2020] T. Peng, A. W. Harrow, M. Ozols, and X. Wu, Simulating large quantum circuits on a small quantum computer, Phys. Rev. Lett. 125, 150504 (2020).
  * Perlin  _et al._ [2021] M. A. Perlin, Z. H. Saleem, M. Suchara, and J. C. Osborn, Quantum circuit cutting with maximum-likelihood tomography, npj Quantum Inf. 7, 1 (2021).
  * Ayral  _et al._ [2020] T. Ayral, F.-M. Le Régent, Z. Saleem, Y. Alexeev, and M. Suchara, Quantum divide and compute: Hardware demonstrations and noisy simulations, in  _2020 IEEE Computer Society Annual Symposium on VLSI (ISVLSI)_ (IEEE, 2020) pp. 138–140.
  * Ayral  _et al._ [2021] T. Ayral, F.-M. L. Régent, Z. Saleem, Y. Alexeev, and M. Suchara, Quantum Divide and Compute: Exploring The Effect of Different Noise Sources, arXiv:2102.03788 [quant-ph] (2021), arXiv: 2102.03788.
  * Tang  _et al._ [2021] W. Tang, T. Tomesh, J. Larson, M. Suchara, and M. Martonosi, CutQC: Using Small Quantum Computers for Large Quantum Circuit Evaluations, in  _Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems_ (Association for Computing Machinery, New York, NY, USA, 2021) pp. 473–486, arXiv: 2012.02333.
  * Tóth and Gühne [2005] G. Tóth and O. Gühne, Entanglement detection in the stabilizer formalism, Phys. Rev. A 72, 022340 (2005).
  * Gühne and Tóth [2009] O. Gühne and G. Tóth, Entanglement detection, Phys. Rep. 474, 1 (2009).
  * Gong  _et al._ [2019] M. Gong, M.-C. Chen, Y. Zheng, S. Wang, C. Zha, H. Deng, Z. Yan, H. Rong, Y. Wu, S. Li, F. Chen, Y. Zhao, F. Liang, J. Lin, Y. Xu, C. Guo, L. Sun, A. D. Castellano, H. Wang, C. Peng, C.-Y. Lu, X. Zhu, and J.-W. Pan, Genuine 12-Qubit Entanglement on a Superconducting Quantum Processor, Phys. Rev. Lett. 122 (2019).
  * Raussendorf and Briegel [2001] R. Raussendorf and H. J. Briegel, A one-way quantum computer, Phys. Rev. Lett. 86, 5188 (2001).
  * Nielsen [2006] M. A. Nielsen, Cluster-state quantum computation, Rep. Math. Phys. 57, 147–161 (2006).
  * Barends  _et al._ [2014] R. Barends, J. Kelly, A. Megrant, A. Veitia, D. Sank, E. Jeffrey, T. C. White, J. Mutus, A. G. Fowler, B. Campbell, _et al._ , Superconducting quantum circuits at the surface code threshold for fault tolerance, Nature 508, 500 (2014).
  * Martinis and Geller [2014] J. M. Martinis and M. R. Geller, Fast adiabatic qubit gates using only ${\sigma}_{z}$ control, Phys. Rev. A 90, 022307 (2014).
  * Bravyi  _et al._ [2021] S. Bravyi, S. Sheldon, A. Kandala, D. C. Mckay, and J. M. Gambetta, Mitigating measurement errors in multiqubit experiments, Phys. Rev. A 103, 042605 (2021).
  * Geller [2021] M. R. Geller, Conditionally rigorous mitigation of multiqubit measurement errors, Phys. Rev. Lett. 127, 090502 (2021).
  * Maciejewski  _et al._ [2020] F. B. Maciejewski, Z. Zimborás, and M. Oszmaniec, Mitigation of readout noise in near-term quantum devices by classical post-processing based on detector tomography, Quantum 4, 257 (2020).
  * James  _et al._ [2005] D. F. James, P. G. Kwiat, W. J. Munro, and A. G. White, On the measurement of qubits, in  _Asymptotic Theory of Quantum Statistical Inference: Selected Papers_ (World Scientific, 2005) pp. 509–538.
  * [37] All data and codes for processing the data can be found in https://github.com/AlaricCheng/simulating_large_LC_states.

##  I Supplemental Material

###  I.1 Processor Performance

Our superconducting quantum processor has 12 frequency-tunable transmon qubits
lying on a 1D chain, and the qubits are capacitively coupled to their nearest
neighbors (the coupling strength is about 12 MHz). Each qubit has a microwave
drive line (XY), a fast flux-bias line (Z) and a readout resonator. All
readout resonators are coupled to a common transmission line for state
readout. In our experiments, four qubits are chosen from the quantum
processor. The performances of the four qubits we chosen in our experiment are
listed in Table S1.

| $Q_{3}$ | $Q_{4}$ | $Q_{5}$ | $Q_{6}$
---|---|---|---|---
$\omega_{01}$ (GHz) | 4.916 | 4.352 | 5.081 | 4.195
$\eta$ (MHz) | -246 | -203 | -247 | -202
$T_{1}$ ($\mu$s) | 45.7 | 35.7 | 29.8 | 33.5
$T_{2}^{*}$ ($\mu$s) | 3.99 | 2.93 | 8.14 | 2.33
$f_{00}$ (%) | 95.0 | 94.3 | 96.9 | 92.2
$f_{11}$ (%) | 90.9 | 91.0 | 90.1 | 88.7
single-qubit gate fidelity (%) | 99.93$\pm$0.07 | 99.97$\pm$0.10 | 99.90$\pm$0.08 | 99.91$\pm$0.17
CZ fidelity (%) |  97.3$\pm$1.7 98.9$\pm$2.0 99.2$\pm$2.2
Table S1: Performance of qubits. $\omega_{01}$ is the idle frequency of qubit.
$\eta$ is the anharmonicity. $T_{1}$ is the energy relaxation time.
$T_{2}^{*}$ is the dephasing time extracted from Ramsey experiment. $f_{00}$
($f_{11}$) is the probability of correctly readout of qubit state in $\ket{0}$
($\ket{1}$) after being well prepared in $\ket{0}$ ($\ket{1}$). Single-qubit
gate fidelities and CZ gate fidelities are characterized by randomization
benchmarking.

###  I.2 Complementary Data For 12-qubit Linear-Cluster State

In the main text, we present experimental distributions from the 3-qubit and
4-qubit linear-cluster states in the $XZ$ measurement basis in Fig 3 (a), and
the expectations of terms from $\mathsf{ODD}$ in Fig. 4 (a). Here, we give the
complementary data from the $ZX$ measurement basis and from the
$\mathsf{EVEN}$ operator. Fig. S1 (a) gives the probability distributions from
the 4-qubit and 3-qubit linear-cluster state, and the theoretical
distributions are also provided for a comparison. Fig. S1 (b) presents the
expectations from the expansion terms in $\mathsf{EVEN}$ for the 12-qubit
linear-cluster state, which can be obtained from the $ZX$ measurement.
Combining the expectations for $\mathsf{ODD}$ and $\mathsf{EVEN}$, one can
derive a fidelity lower bound using,

$\displaystyle\Tr(\rho\outerproduct{\mathsf{LC}_{n}}{\mathsf{LC}_{n}})\geq\Tr(\rho\mathsf{ODD})+\Tr(\rho\mathsf{EVEN})-1\
,$ (S1)

as discussed in the main text.

Figure S1: (a) The output distributions from $ZX$ measurement of the 4-qubit
and 3-qubit linear cluster states. (b) Comparison of the expectations with
$XZ$ measurement obtained from the 12-qubit circuit [28] (orange) and from the
circuit-cutting scheme by running smaller quantum circuits (blue). Each bar
corresponds to one specific observable in $\mathsf{EVEN}$ and there are 64
expectations for each group. The ideal values of all these expectations are
one.