# Augmentix - An Augmented Reality System for asymmetric Teleteaching

Nico Feld<EMAIL_ADDRESS>University of TrierUniversitätsring
15TrierGermany56290

###### Abstract.

Using augmented reality in education is already a common concept, as it has
the potential to turn learning into a motivational learning experience.
However, current research only covers the students site of learning. Almost no
research focuses on the teachers’ site and whether augmented reality could
potentially improve his/her workflow of teaching the students or not. Many
researchers do not differentiate between multiple user roles, like a student
and a teacher. To allow investigation into these lacks of research, a teaching
system ”Augmentix” is presented, which includes a differentiation between the
two user roles ”teacher” and ”student” to potentially enhances the teachers
workflow by using augmented reality. In this system’s setting the student can
explore a virtual city in virtual reality and the teacher can guide him with
augmented reality.

augmented reality, virtual reality, teleteaching, teleeducation, tangibles,
collaborative virtual environment

††copyright: rightsretained

##  1\. Introduction

Technologies such as augmented reality (AR) have the potential to enrich the
physical world with virtual content by augmenting the physical environment by
digital information. This combination of (mixing) a physical with a virtual
environment may simplify the interaction with this virtual content as the user
still has reference to the physical, known environment (Zhou et al., 2008).
Since the technology of augmented reality started to rise, it was examined for
benefits they can bring to teaching and education. Especially since the rapid
improvements in mobile technologies (like smartphones) made them accessible
for a wider audience.

Therefore, one scenario which we think could greatly benefit from using
augmented reality would be virtual classrooms. The students can freely move
around a virtual environment and the teacher does use AR to guide them through
the virtual environment and teach them about a specific topic. This scenario
does not only allow distributed users to participate in such a learning
experience, but technologies like AR could further improve their experience
(Sommerauer and Müller, 2018).

Furthermore we think that AR could also improve the workflow of the guide. By
the combination of the real physical environment and the virtual environment
AR provides natural and intuitive interaction, especially with the usage real
objects being used to interact with he virtual environment, called ”Tangibles”
(Billinghurst et al., 2015). This could allow the guide to teach the student
in a natural and intuitive way, as he/she would do in a real city tour,
without having to adapt his/her workflow as much as he would need to with non-
AR system.

Considering this scenario, we may define this situation as an asymmetric CVE
as defined by Feld & Weyers (Feld and Weyers, 2019) In an asymmetric CVE, they
specify two user roles. A primary is a user who controls the CVE and
contributes most of the content. A secondary on the other hand is a user who
mostly consumes this content and only have minor contribution. In an typical
asymmetric teleteaching CVE, a teacher would be a primary while the students
would be multiple secondaries, as the teacher is providing the information the
students are consuming. In a symmetric CVE, every user has the same role and
therefore every user contributes equally. A typical symmetric CVE would be a
virtual room for autonomous group work.

While Feld & Weyers only found two examples for symmetric CVEs systems for
teaching (Ibáñez et al., 2012; Santos et al., 2014) using AR they found no
asymmetric CVE for teaching. The authors of this paper additionally found one
system where one user had another role as the others (Bower et al., 2017), but
this only included the ability to show slides. Therefore, there is a lack of
research regarding asymmetric CVEs with AR the scenario we suggested, where
there is one teacher and multiple students.

In addition Feld & Weyers also found no examples for asymmetric CVE where the
primary uses AR to control and contribute to the CVE. Every usage of AR in the
research found was limited to the secondaries to turn learning into a
motivational learning experience (Sommerauer and Müller, 2018), but never
tackles the question if AR could potentially improve their workflow in
teaching secondaries.

Therefore we identified two major research questions about asymmetric CVEs
using AR for a system implementing the given scenario:

  1. (1)

How to design an asymmetric CVE in context of education?

  2. (2)

Can a primary benefit from AR?

To answer these questions, we present the asymmetric CVE for teaching
Augmentix by implementing the suggested scenario. In this system, the primary
uses AR to control the CVE and the secondaries are guided by the primary
through an virtual environment. In the prototype of Augmentix the secondaries
can have a virtual city tour in virtual reality (VR) through an antic version
(400 A.D.) of the german city Trier. This city tour then is guided by a
primary, who is in his office using AR.

In this paper, CVE describes the whole environment both the primary and the
secondaries are in, therefore the primaries virtual and physical environment
and the secondaries virtual environment. This CVE is visualized in figure 1.
The virtual environment of the secondary describes the environment the
secondary is in. In the case of Augmentix, this is a virtual representation of
the antic Trier. The primaries environment on the other hand is split into
his/her physical environment and a virtual environment for augmentation.

Figure 1. The CVE of Augmentix

To design and implement a system for this scenario, first requirements of this
system get derived (section 2). Based on these requirements, a workflow is
designed (section 3), which then is implemented in a prototype (section 4).
This prototype then was evaluated in a small expert interview (section 5).
Based on the findings of this interview the results were discussed and
concluded (section 6) and potential future work is defined (section 7).

##  2\. Requirements

To implement a prototype for the given scenario, the system must meet certain
design requirements (DR). Based on these DRs we concluded certain technical
requirements (TR). In the following first the DRs are defined and then the
resulting TRs are listed.

###  2.1. Design requirements

For this scenario, secondaries need to freely move around the virtual city and
the primary can then focus on one secondary to communicate with him and guide
him through the city. To do this, the primary must be able to display
additionally information to the secondary and manipulating the CVE. To allow
the primary to display the correct information, he/she must know the virtual
environment of the secondary. Furthermore, the primary needs to also be able
to interact with his/her real environment to be able to test possible
enhancements in his/her workflow to answer the two identified research
questions. Therefore we define the following requirements:

  1. DR 1.

Communication

    1. 1.

The primary and secondaries need to communicate

    2. 2.

The primary needs to see the secondary and his/her virtual environment

    3. 3.

The primary needs to steer the attention of the secondary towards certain
points of interest

  2. DR 2.

Interaction

    1. 1.

The primary needs to interact and manipulate the CVE

    2. 2.

The primary needs to show additional information to the secondary

    3. 3.

The primary needs to use AR

    4. 4.

The primary needs to potentially switch between multiple secondaries

  3. DR 3.

Navigation

    1. 1.

The secondary needs to freely move inside the CVE

    2. 2.

The primary needs to interact with the secondary regardless their position in
the environment

###  2.2. Technical requirements

Based on these DRs we identified the following technical requirements:

  1. TR 1

Network Connection between both parties

  2. TR 2

Communication devices for both parties

  3. TR 3

AR-Display Device for primary

  4. TR 4

Input Device for primary

  5. TR 5

Tangibles for primary

  6. TR 6

Display & Input Device for secondary

Because the users are using the same CVE, some sort of network connection
between the users is mandatory for this system (TR 1), to synchronize the two
local environments. To let the primary and secondaries communicate (DR 1.1)
some sort of communication device is needed (TR 2). To display the virtual
environment to the primary (DR 1.2, DR 1.3, DR 2.1, DR 2.2 and DR 3.2) a
display device is needed. To further meet DR 2.3 this display device must must
support AR (TR 3). These also lead to TR 4 as the primary must also have a way
to interact with the CVE. In Augmentix, we decided to use a common smartphone
as an AR display and input device. This also meets TR 2 as the built in
microphone can be used. In future work this system can be extended to support
an AR-HMD (eg. Hololens 2), as this allows an immersive experience and
supports full hand tracking, which could further improve the primaries
workflow.

To let the primary interact with the CVE (DR 2.1) while using AR (DR 2.3) to
interact with his real environment the authors used tangibles (TR 5), as they
can be used as an physically-based interface metaphor (Billinghurst et al.,
2008).

To meet DR 3.1 the secondary needs a display and input to move freely inside
the CVE. In this system, he/she uses virtual reality to immerse him-/herself
into and interact with the CVE (TR 6). As research showed VR, like AR, can
create a motivational learning experience (Borst et al., 2018) and therefore
the authors decided to implement the secondaries site with VR.

##  3\. Workflow and Implementation

”Augmentix” was designed with support for multiple secondaries in mind. While
the technical implementation only supports one secondary in this prototype,
the workflow was defined for multiple secondaries (DR 2.4).

When the secondary starts Augmentix he/she is directly put into the virtual
environment and can start freely exploring via the teleport metaphor. Because
the teleport metaphor does only allow to teleport for a short distance, the
secondary does have a map of the virtual environment attached to his/her left
hand. This map can be shown and hidden via pressing a button and show buttons
for every major POI in the virtual environment. By clicking one of those
button on the map, the secondary is teleported to this POI. With the short
teleport and the teleport to POIs DR 3.1 is fulfilled.

The primary site of the CVE on the other hand was divided into two major
parts. The ”Map-Hub” and the ”Pickup-Shovel”. The Map-Hub should give an
overview to the primary about the position of the secondaries and allow him to
pick one which he/she wants to further interact with. The primary can return
to the Map-Hub at any time for an overview or to focus on another secondary.
To meet DR 2.3 the Map-Hub was realized with AR in mind. Therefore a real map
of the antic Trier was augmented and the secondaries are displayed with a
arbitrary avatar on their position inside the city. The primary can walk up
upon this map and can see all the secondaries and their position in the city.

(a) The Map-Hub as seen by the primary (secondary marked with a red arrow

(b) The corresponding view of the secondary

Figure 2. The Map-Hub and the corresponding view of the secondary

Figure 2(a) shows the Map-Hub with the position of a secondary and the
corresponding view of the secondary standing in front of the ”Porta Nigra” is
shown by figure 2(b).

Any secondary can now be picked up by using a shovel-metaphor with the
”Pickup-Shovel”. Therefore the primary can hold the Pickup-Shovel next to a
secondary on the Map-Hub to pick him/her up. If this action was performed
successfully, the secondary is no longer displayed on the Map-Hub but on the
Pickup-Shovel. This allows the primary to move the secondary anywhere in
his/her real physical environment. For example by placing the Pickup-Shovel on
his desk the primary can now view and interact with the secondary while
sitting in front of his desk, instead of standing in front of the Map-Hub.
Furthermore, the virtual environment of the secondary is now also displayed to
the primary (DR 1.2).

A voice chat can now be started by the primary via a toggle-button on his/her
UI, so that both users can communicate with each other (DR 1.1). To keep an
overview of the environment the primary can adjust the scale via a slider. If
the primary wants to have an overview of the surroundings he/she can scale the
environment down and if the wants to interact with a smaller object he/she can
scale the environment up to allow more precise interactions. By default the
primaries position remains on the center of the pickup-shovel. Therefore if
the secondary moves around in his/her environment on the primaries view the
environment is moving rather than the secondary. As this allows the primary to
keep focus on the secondary, this mode makes it difficult to interact with the
environment while the secondary is moving. Therefore, the primary can change
the camera-mode to remain relative to the environment rather than following
the secondaries position with an toggle-button in the interface. This allows
the primary to interact with the secondary regardless of his/her position in
the virtual environment (DR 3.2). Figure 3 shows the primaries interface when
interacting with the secondary. The toggle-button ”Audio Stream” on the top
right enables or disables the voice chat, the toggle-button ”LockCam” on the
bottom left changes the camera mode and the slider on the bottom left allows
changing the scale. The red ”X”-button removes the secondary from the Pickup-
Shovel and places him/her back into the Map-Hub, so that the primary can
pickup another secondary. The secondary currently does not have any indication
if he/she is currently picked up or at the Map-Hub. This could change in
future work, as an indication could possibly change the secondaries behaviour
and motivation to explore.

Figure 3. Interface for primary while interacting with a secondary

To allow interaction with the surroundings the environment contains ”objects
of interest” (OOI). By tapping on one of these OOI, on the smartphone a
context menu appears that enables various interactions. These interactions
vary depending on the OOI selected, as they can be turned on and off and
edited for every OOI beforehand. Current implemented interactions are:

  * •

Display Text

  * •

Display Video

  * •

Scale

  * •

Highlight

  * •

Change

  * •

Lock

The first two interactions are for displaying additional information about the
OOI (DR 2.2). When clicking on either the ”Text” or the ”Video”button, a text-
box or a video screen appears in front of the secondary. The text and the
video must also be set beforehand. With the ”Scale” interaction enabled, the
primary can adjust the scale of the OOI via a slider. ”Highlight” draws an
outline around the OOI for both users and displays an arrow to the secondary
pointing towards the OOI. This arrow gets removed when the secondary is next
to the OOI and is looking towards it. This interaction can be used by the
primary to steer the focus of the secondary (DR 1.3). The ”Change” interaction
allows the primary to change the OOI into another OOI via a dropdown menu

To let the primary create new OOIs for example to create context related OOIs
to substantiate facts, Augmentix uses Tangibles. As seen in figure 4(a) when
placed within the view port of the smartphones camera, the tangible gets
highlighted on the screen and the primary can tap on the tangible to display a
dropdown menu. Figure 4(b) shows the dropdown menu with the list of all
possible OOIs the primary can create. By selecting one of the corresponding
OOI, it gets created in the CVE, thus visible for both users. If the primary
now physical moves the tangible around the primary, the created OOI now moves
in the secondaries environment simultaneously. Therefore the primary can now
place new OOIs next to other OOIs to compare these two.

(a) Tangible without an attached OOI

(b) The dropdown menu to select a new OOI

(c) The context menu of the new OOI

Figure 4. Workflow of the Tagibles

Figure 4 shows this workflow of creating a new OOI via a tangible.

With the last interaction ”Lock”, the primary can lock the position of the
OOI, so that it does not longer follow the movement of the tangible. This is
done via a click on the lock-symbol. The primary then can use the tangible to
add another OOI. A locked OOI can also then be removed by a red trashcan-
button. If an empty tangible is held next to an OOI it can be attached back
onto the tangible by clicking the lock symbol again. Figure 4(c) does show the
OOI ”Porta Nigra” currently attached to an tangible with the interactions
”Display Text”, ”Display Video”, ”Scale”, ”Change” and ”Lock” enabled. With
the tangibles and the implemented interactions the primary can interact and
manipulate the CVE and therefore DR 2.1 and DR 2.3 are met. A summary and
overview of the solutions for the DRs are given in table 1.

Design Requirements | Solutions
---|---
DR 1.1 | Voice chat
DR 1.2 | Pickup-Shovel
DR 1.3 | Highlight-Interaction
DR 2.1 | Interactions and OOIs
DR 2.2 | Display Text/Video
DR 2.3 | Map-Hub, Pickup-Shovel
| and Tangibles
DR 2.4 | Map-Hub
DR 3.1 | Teleport and POI-Teleport
DR 3.2 | Multiple Camera modes
Table 1. Solutions to the design requirements

With this proposed workflow all DRs are met. The next section does cover the
technical implementation of this workflow.

##  4\. Implementation

This system was implemented using the ”Unity” 3d game engine (Technologies,
2019). Unity allows to create 3d games for various platforms like mobile
devices (android, iOS) or desktop pcs (windows, linux, macOS).

###  4.1. Augmented reality

The augmented reality part of Augmentix is implemented with ”Vuforia” (PTC,
2019b) and therefore these definitions only focus on marker-based tracking. An
”augmentation entity” describes an entity which is in a CVE used for AR. This
entity consists of two major parts: a physical prop and a virtual
representation in unity. The physical prop gets tracked in the real physical
environment and its position and rotation gets mapped onto the virtual
representation to let the virtual representation move like the physical prop
does. In Augmentix the physical props are just images printed out, also called
”Markers”. The virtual representation of these markers are called ”Image
Targets” in Vuforia. In Augmentix there are five augmentation entities:

  * •

The Map-Hub

  * •

The Pickup-Shovel

  * •

3x Tangibles

Therefore 5 unique markers were needed. These where randomly chosen images
from the internet, themed in the antic age. As Vuforia allows to test images
for their ability to be used as markers. Only images with the highest rating
were used to minimize tracking issues. These images were then printed and
stuck onto a map of Trier (Map-Hub), as small wooden shovel (Pickup-Shovel) or
three small wooden chips (Tangibles) to enable physical interactions as seen
in figure 5.

Figure 5. The physical props with their markers attached

To be able to scale all the game objects of one image target a dummy game
object named ”Scaler” is created as a child of each image target. Each game
object for augmentation now gets attached as a child of the Scaler. If the
Scaler is now scaled or moved, all the underlying game objects are scaled or
moved aswell. This can be used to create an offset of the augmentation or to
scale it all at once.

To implement the Map Hub one of these images was put on top of a real map.
First test to use the map itself as a marker failed, as it has to few feature
points, which are needed to be a good augmentable image (PTC, 2019a). Because
the position of the secondaries in the Map Hub should not be based on the
position of the image but rather on the position of the map, the offset
between the center of the image and the origin in the secondaries virtual
environment must be considered when placing Game Objects.

Figure 6. Visualisation of the origin of the Map Hub

The offset can be created my moving the Scaler to the position the origin of
the virtual environment of the secondary is on the map. A visualization of
this can be seen in figure 6 where the center of the image is marked red, the
origin of the virtual environment of the secondary is marked blue and the
position of the player green. The brown line therefore shows the final offset
from the image to the players position. The origin of the virtual environment
of the secondary has been arbitrarily been chosen when the virtual
representation of Trier was created.

Another image is also attached to the physical Pickup Shovel. When the image
gets tracked by the primary holding the Pickup Shovel in the cameras view, the
distant of the corresponding Image Target and the secondary on the Map Hub get
calculated and if it is under a predefined threshold the secondary gets put as
a child of the Scaler of the Pickup Shovel. Therefore the secondary is now
following the Pickup Shovels position and the primary can now place the
secondary somewhere else.

The Tangibles are similar to the Pickup Shovel regarding their implementation
with AR. An image is attached to a wooden chip to be able to track it. When
creating a OOI now as a child of the corresponding image target, the OOI is
following the Tangibles position.

###  4.2. Interface

The interface was implemented with the standard UI provided by Unity. These
include common input types, like text-fields, buttons, drop-down menus and
sliders. The interface is divided into two parts. While the ”AR-UI” is used
for any interactions with the virtual environment and can easily be
implemented with the standard UI, the ”OOI-UI” is used to interact with a
selected OOI. Therefore the OOI-UI always in context to an specific OOI. To
visualize this context the OOI-UIs position is always following the OOIs
position. Because the OOIs position is in 3D space and the OOI-UIs position is
on the 2D screen-plane a projection based on the cameras projection matrix has
to be made. Figure 4(c) does show the positioning of the OOI-UI in context to
the selected OOI. Because the amount of button representing different
interactions (see section 3 is dependent on the OOI selected the positions of
these buttons must adjusted according this amount. Therefore the buttons get
arrange in a circle around the OOI. The distance of the arc between the
different buttons is dependent on their amount. The final equation for the
position is:

    x = Radius * Screen.width / 100
        * Math.Cos(2 * i * Math.PI / Buttons.Count)
    y = Radius * Screen.height / 100
        * Math.Sin(2 * i * Math.PI / Buttons.Count)

Where $Radius$ is a predefined constant which defines the percentual radius of
the circle in proportion to the given screen space and $i$ is the index of the
current Button.

###  4.3. Network

For the communication between the users the framework ”Photon” by Exit Games
was used (Games, 2019). This framework includes various networking-libraries
for different aspect of network communication. We used ”PUN” for the
synchronisation of and interaction with the virtual environment and ”Voice”
for the implementation of the voice chat. Each game object that should be
synchronized with PUN must have a ”PhotonView”-Component. This component
handles the global indexing of these objects in the network and defines an
owner of this game object. If various properties or components of this game
object should be synchronized additional views can be added. These views then
define which properties of a game object are synchronized and how they are
synchronized. One game object can have multiple views handling various
properties. Therefore a game object which synchronizes its transform and for
example a health-component can do this via a transform-View and a health-View
where the synchronization is handled. Some of these additional views, like a
transform view are already provided. Because the original transform-view only
handles the global position of objects and in the primaries virtual
environment all synchronized objects are children of image targets, this view
had to be adjusted to synchronize local positions rather than global
positions. A custom transform-view was also needed to synchronize the
positions of OOIs attached to a Tangible. Because the OOI is a child of the
tangible and therefore in another coordinate system, its local position must
first be calculated into the local coordinate system of the virtual
environment of the secondary. Thus the position of the OOI can correctly be
set in the virtual environment of the secondary. This projections into
different local coordinate systems are provided by Unity.

Because all game object used must be available to all users, every game object
synchronized over the Network, which is not a part of the scene from the
beginning, must be defined as a prefab-asset in the ”Resource” folder of the
project. Is is especially necessary because Unity does optimize the system
when build, by removing all unused assets. Therefore if an asset is not used
in a scene it will get removed by unity and can’t be used at runtime. An
exception to this behaviour is the ”Resource” folder. This one does get
ignored by unity and every asset inside this folder is available at runtime.
These assets include:

  * •

A player avatar

  * •

the virtual representation of the city

  * •

every OOI creatable with a Tangible

A player avatar get created for each user every time a new secondary is
starting their application and synchronize their transform with each user.
Additionally a instance of the virtual representation for the city gets
created for the secondary to walk in and for the primary. On the primary site
this representation gets hidden first and then is later used, by making it
visible again, in the Pickup-Shovel to show the surroundings of the secondary
to the primary.

##  5\. Expert interview

To validate the system and the workflow we conducted an expert interview. In
this interview six computer scientist separately were first introduced into
the concept and the goal of this system. Then they could freely try the
secondaries site of this system to get familiar with the secondaries virtual
environment and interactions. After that they got introduced into the workflow
and the system of the primary and then could freely try the primaries site and
get used to the workflow and all interactions provided by Augmentix.
Subsequently they were asked to perform specific tasks to guide a student
through a staged virtual city tour. These tasks can be found in the
attachments. The secondary was here played by one of the authors of this paper
and intentionally forced the expert to use all provided interactions. After
the tasks were successfully completed the expert was asked a eight questions
about his/her experience. These questions aimed at the functionality of the
system and the advantages and disadvantages the usage of AR. These questions
can be found in the attachments. The answers to these questions were
anonymously recorded, transcribed and translated from german to english
afterwards.

Usage of AR |  E2: ”… can better assess the behaviour of the user, because I am more immersed” | I.a
---|---|---
|  E3: ”[The interaction] is very natural … therefore i think for normal city tour guides [this system] is better, than a desktop environment …” | I.b
|  E4: ”to place the [objects] in the view of the player was quite fiddly … i think this will be easier with a mouse” | I.c
Workflow |  E1: ”… it was cool … nothing to complain.” | II.a
|  E5: ”I think it is difficult with two planes (work spaces) … you could project the Map-Hub onto the desk” | II.b
|  E2: ”I like the metaphor, but i don’t think it does scale well [with multiple students].” | II.c
Interaction |  E1: ”.. can not put tangibles very close to each other in the real world.” | III.a
|  E2: ”It was confusing … to change the interaction space.” | III.b
|  E5: ”I always tried to click on the [physical] tangibles. | III.c
|  E1: ”[The interface] was quite intuitive …” | III.d
Features |  E3: ”I think … a rotation … could be very helpful and make [the guidance] easier. ” | IV.a
|  E2: ”Pointing would be a nice feature, like ’Hey, look here’ | IV.b
|  E5: ”What could be more intuitive is if the scaling could be done via a [multitouch] gesture | IV.c
Technical Aspects |  E2: ”I see a big disadvantage in the mobile phone …” | V.a
|  E3: ”Depending on the amount of students … i think two [free] hands are clearly superior.” | V.b
|  E1: ”The buttons are really close to each other” | V.c
|  E6: ”I couldn’t really see where you were facing” | V.d
Table 2. Expert feedback

While all experts think that the usage of AR as a primary is very intuitive,
immersive and motivational I.a,I.b, they also think that at the current stage
this system is to inconvenient to use for an efficient and long term usageI.c.
One major factor for this inconvenience was the usage of a smartphone V.b,V.c.
To view the virtual content the smartphone must be always held in view and
therefore all the interactions can only be performed with a single hand. As
this flaw was suspected and therefore two questions specifically focused on
this topic, the expert interview confirmed that the smartphone had an
significant negative impact on the performance and experience of the primary.
However because of the intuitive interactions three experts stated that they
see a big advantages for users as primary who are no experts in computer
systems in comparison to a potential system using a common desktop environment
I.b. But on the other hand a system using a desktop environment would probably
be more efficient for users once they get familiar with this system. To
counter these problems five experts suggested the use of an AR HMD as this
would allow the primary to use both hands for interactions. Three experts
further suggested a stand, like a tripod, for the smartphone if no HMD is
available.

The workflow of the Map-Hub and the Pickup-Shovel was according to all experts
easy to understand and convenient to use II.a,II.c. However all experts think
that this workflow does not scale well with multiple secondariesII.c. While
the pickup-metaphor was easy to understand it would be too tricky and
imprecise to use and the overall overview would suffer when handling multiple
secondaries. Two experts also stated that they think merging the Map-Hub and
the Pickup-Shovel into one plane could improve this workflow, as both work
spaces are then always in the field of view of the primaryII.b.

The interface and the interactions were received well by all experts. The
interface was clear and easy to understand. Only the buttons sometimes
overlapped and then were hard to click onV.c. No expert missed an interaction
method while performing the tasks. The usage of tangibles were also described
as intuitive and easy, merely the physical prop was perceived as too clunky to
perform precise interactions with them III.a. Furthermore two experts were
bothered by the repeating context switch between the physical tangibles and
the interface of the smartphoneIII.b,III.c. Further two experts stated that
the secondaries view direction was not clear enoughV.d. As potential new
features three experts proposed a 3D pointing interaction for the primary to
highlight not only objects but to point on specific areas in the environment,
like a laser pointerIV.b. Furthermore, three experts proposed a forced
rotation on the secondary to guide his/her focus additionally to the already
implemented highlight interactionIV.a. A support of multi-touch gestures, like
a pinch gesture, were proposed by five experts, as it would use the already
known gestures used my common smartphone applicationsIV.c. Furthermore three
experts had technical problems, as the system did not always detect the images
for the Image Targets, because they unintentional blocked the view of these
images while interacting with the tangibles.

Because in the interview the primary and the secondary were in the same room
the usage of the provided voice chat was not needed. Nevertheless all experts
stated that a voice chat would probably be sufficient to communicate with the
secondary in a distributed setup and don’t see any necessity for additional
communication channels. Two experts stated however that the secondary could
possible benefit from a video chat, because he could be feel more engaged with
the primary when seeing him via a video chat.

##  6\. Discussion & Conclusion

While the expert interview showed, that the usage of AR as a primary does
potentially provide a intuitive and immersive experience, in the current stage
it does not enhance the workflow of the primary in comparison to a potential
system using a common desktop environment. One major drawback was the usage of
a common smartphone as an input and display device. Therefore the technical
implementation of AR has a huge impact on the experience of the primary.
Furthermore the proposed workflow was well received in terms of design and
usability, but, according to the expert interview, will not scale well with
multiple students. This leads to the conclusion, that the workflow must not
only be designed in terms of usability and complexity, but must be efficient
and scaleable, aswell. Therefore the current workflow does not provide the
desired enhanced experience for the primary. The interface was well received
and the interaction methods were easy to understand, therefore only minor
tweaks are necessary to optimise these aspects. But the interface and the
interaction methods heavily depend on the implementation of AR. In this first
prototype these were designed for a smartphone, but if AR is implemented with
a HMD the interface and the interaction methods must be completely redesigned.
In terms of communication channels the provided voice chat was stated as
sufficient and therefore no additional channels are needed.

These results lead to the conclusion that this first prototype of Augmentix is
not sufficient enough to tackle the two research questions identified in
section 1. While the experts stated that this system is easy, intuitive and
immersive, no positive aspects on performance were identified. But we think
that all the negative aspects can be addressed and a positive aspects in
performance can be achieved by the usage of AR.

##  7\. Future Work

In potential future work first the negative technical aspects should be
addressed. The authors suggest research which implements AR with a HMD to
allow a more immersive and intuitive interaction. Further the tangibles could
be upgraded to allow more physical interactions. A physical button or switch
could minimize the need of context switches, which had a negative impact in
this first prototype of Augmentix.

In addition a more scalable and efficient workflow must be designed. Though
the current workflow is easy and intuitive it was stated as not scalable and
efficient by the experts. To achieve significant results the potential new
workflow must be validated in a study with multiple secondaries in one
sitting.

To finally validate such a system using AR to enhance the primaries workflow,
a desktop application for guiding a secondary through a virtual city must be
designed. As such a system is needed to verify the results claimed about a
system using AR.

## References

  * (1)
  * Billinghurst et al. (2015) Mark Billinghurst, Adrian Clark, and Gun Lee. 2015.  A Survey of Augmented Reality.  _Foundations and Trends® in Human–Computer Interaction_ 8, 2-3 (2015), 73–272.  https://doi.org/10.1561/1100000049
  * Billinghurst et al. (2008) Mark Billinghurst, Hirokazu Kato, and Ivan Poupyrev. 2008\.  Tangible augmented reality.  _ACM SIGGRAPH ASIA 2008 Courses_ (01 2008).  https://doi.org/10.1145/1508044.1508051
  * Borst et al. (2018) Christoph Borst, Nicholas Lipari, and Jason Woodworth. 2018\.  Teacher-Guided Educational VR: Assessment of Live and Prerecorded Teachers Guiding Virtual Field Trips. 467–474.  https://doi.org/10.1109/VR.2018.8448286
  * Bower et al. (2017) Matt Bower, Mark J. W. Lee, and Barney Dalgarno. 2017\.  Collaborative learning across physical and virtual worlds: Factors supporting and constraining learners in a blended reality environment.  _British Journal of Educational Technology_ 48, 2 (3 2017), 407–430.  https://doi.org/10.1111/bjet.12435
  * Feld and Weyers (2019) Nico Feld and Benjamin Weyers. 2019.  Overview of Collaborative Virtual Environments using Augmented Reality. In _Mensch und Computer 2019 - Workshopband_. Gesellschaft für Informatik e.V., Bonn.  https://doi.org/10.18420/muc2019-ws-617
  * Games (2019) Exit Games. last visited 06.11.2019.  Photon.  https://www.photonengine.com/en-US/Photon.
  * Ibáñez et al. (2012) María Blanca Ibáñez, David Maroto, José Jesús García Rueda, Derick Leony, and Carlos Delgado Kloos. 2012.  Architecture for Collaborative Learning Activities in Hybrid Learning Environments.  18, 15 (aug 2012), 2187–2202.
  * PTC (2019b) PTC. last visited 29.10.2019b.  Vuforia 8.5.  https://www.ptc.com/en/products/augmented-reality.
  * PTC (2019a) PTC. last visited 30.10.2019a.  Optimizing Target Detection and Tracking Stability.  https://library.vuforia.com/articles/Solution/Optimizing-Target-Detection-and-Tracking-Stability.
  * Santos et al. (2014) Marc Ericson Santos, Angie Chen, Takafumi Taketomi, Goshiro Yamamoto, Jun Miyazaki, and Hirokazu Kato. 2014.  Augmented Reality Learning Experiences:Survey of Prototype Design and Evaluation.  _Learning Technologies, IEEE Transactions on_ 7 (02 2014), 38–56.  https://doi.org/10.1109/TLT.2013.37
  * Sommerauer and Müller (2018) Peter Sommerauer and Oliver Müller. 2018.  Augmented Reality for Teaching and Learning-a literature Review on Theoretical and Empirical Foundations.. In _ECIS_. 31.
  * Technologies (2019) Unity Technologies. last visited 29.10.2019.  Unity 2019.3.0b4.  http://unity.com.
  * Zhou et al. (2008) Feng Zhou, Henry Duh, and Mark Billinghurst. 2008.  Trends in Augmented Reality Tracking, Interaction and Display: A Review of Ten Years of ISMAR.  _2008 7th IEEE/ACM International Symposium on Mixed and Augmented Reality_ 2, 193–202.  https://doi.org/10.1109/ISMAR.2008.4637362


# Tapping into Permutation Symmetry for Improved Detection of $k$-Symmetric
Extensions

Youning Li  College of Science, China Agricultural University, Beijing,
100080, People’s Republic of China  Chao Zhang  Department of Physics, The
Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong
Kong, China  Shi-Yao Hou  College of Physics and Electronic Engineering,
Center for Computational Sciences, Sichuan Normal University, Chengdu 610068,
China  Zipeng Wu  Department of Physics, The Hong Kong University of Science
and Technology, Clear Water Bay, Kowloon, Hong Kong, China  Xuanran Zhu
Department of Physics, The Hong Kong University of Science and Technology,
Clear Water Bay, Kowloon, Hong Kong, China  Bei Zeng  Department of Physics,
The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon,
Hong Kong, China

###### Abstract

Symmetric extensions are essential in quantum mechanics, providing a lens to
investigate the correlations of entangled quantum systems and to address
challenges like the quantum marginal problem. Though semi-definite programming
(SDP) is a recognized method for handling symmetric extensions, it grapples
with computational constraints, especially due to the large real parameters in
generalized qudit systems. In this study, we introduce an approach that
adeptly leverages permutation symmetry. By fine-tuning the SDP problem for
detecting $k$-symmetric extensions, our method markedly diminishes the
searching space dimensionality and trims the number of parameters essential
for positive definiteness tests. This leads to an algorithmic enhancement,
reducing the complexity from $O(d^{2k})$ to $O(k^{d^{2}})$ in the qudit
$k$-symmetric extension scenario. Additionally, our approach streamlines the
process of verifying the positive definiteness of the results. These
advancements pave the way for deeper insights into quantum correlations,
highlighting potential avenues for refined research and innovations in quantum
information theory.

##  I Introduction

In the intricate domain of quantum mechanics, symmetric extensions stand out
as a cornerstone, providing a structured mathematical lens to explore the
nature and behavior of quantum states. A bipartite state $\rho_{AB}$ is deemed
symmetrically extendible if there exists a multi-partite density matrix
$\rho_{A_{1}A_{2}\ldots A_{m}B_{1}B_{2}\ldots B_{n}}$ such that each of its
reduced density matrices, when traced over its complements, matches
$\rho_{AB}$:

$\operatorname{Tr}_{(A_{j}B_{k})^{c}}(\rho_{A_{1}A_{2}\ldots
A_{m}B_{1}B_{2}\ldots B_{n}})=\rho_{AB},~{}\forall j,k.$ (1.1)

Delving into the importance of symmetric extensions, they serve as a tangible
framework to probe the nature of quantum entanglement, offering a means to
understand the profound correlations present in entangled quantum systems
Horodecki  _et al._ (2009); Bennett and Wiesner (1992); Nielsen and Chuang
(2010). Furthermore, they pave the way for addressing the quantum marginal
problem, which investigates the necessary conditions under which a set of
density matrices can correspond to a global state Klyachko (2006); Chen  _et
al._ (2014). This problem’s universality is showcased by its resonance with
the $N$-representability problem in quantum chemistry Coleman (1963); Erdahl
(1972).

A common approach for identifying a $k$-extension is to cast the problem as a
semi-definite programming (SDP) problem Navascués  _et al._ (2009); Brandão
_et al._ (2011); Johnston (2014). SDP, a form of convex optimization, involves
minimizing a linear function subject to the constraints that the solution lies
in the intersection of the cone of positive semidefinite matrices and an
affine space. Given that density matrices are inherently semidefinite, SDP has
found extensive application in quantum information problems Vandenberghe and
Boyd (1996); Doherty  _et al._ (2004). By leveraging the properties of SDP, we
can devise efficient algorithms for detecting $k$-extensions. For example, the
algorithm used in QETLAB that determines if a bipartite quantum state
$\rho_{AB}$ is $k$-symmetric extendible for the $d$-dimensional subsystem $B$
has the form:

$\displaystyle\mathrm{find}\;\tilde{\rho}$ (1.2) $\displaystyle s.t.$
$\displaystyle\;\begin{cases}\tilde{\rho}\succeq 0\\\
\mathrm{Tr}_{\left(AB_{1}\right)^{c}}\left(\tilde{\rho}\right)=\rho_{AB}\\\
\left(\mathbb{1}_{A}\otimes
P_{ij}\right)\tilde{\rho}\left(\mathbb{1}_{A}\otimes
P_{ij}\right)=\tilde{\rho},\forall i,j\end{cases}$

where $\tilde{\rho}=\rho_{AB_{1}B_{2}\ldots B_{k}}$ is the $k$-symmetric
extension of $\rho_{AB}$ and the operator $P_{ij}$ is an element in
permutation group $S_{k}$. However, the substantial number of real parameters,
notably in the general qudit scenario, can present formidable computational
obstacles. This is largely due to the requirement of the entire extended
Hilbert space $\mathcal{H}_{AB_{1}B_{2}\ldots B_{k}}$, which scales as
$O((d^{2})^{k})$. Such exponential scaling can make calculations intractable
for larger systems or higher dimensions.

In this work we are going to present a new optimization scheme, which not only
considers the permutation symmetry to reduce the total parameters but also
optimize in the subroutine to determine positive definiteness, where the
parameters for single time optimization grows no faster than

$\prod_{m=1}^{d-1}\frac{1}{m!}\left(1+\frac{2k}{d(d+1)}\right)^{d(d-1)/2},$

for large $k$ and $d$.

A testament to our methodology’s effectiveness is its application to the
renowned bipartite Werner state, where it exhibits a pronounced acceleration
in comparison to the established QETLAB software. This enhancement equips us
to approach larger $k$-extension challenges with unparalleled efficiency.

Furthermore, our calculations have explicitly determined the dimensions of the
searching space and the number of parameters required for positive
definiteness tests. This efficiency stems from our algorithm’s ability to
undergo multiple distinct positive-definiteness tests, each correlating to a
unique Young diagram. Each individual test, though involving a significantly
smaller matrix, culminates in a comprehensive and efficient analysis.

Our findings contribute to a clearer understanding of quantum systems,
potentially aiding in the design of more proficient quantum algorithms and
enhancing our grasp of quantum information theory.

The structure of our paper is as follows: Sec. II delves into the intricacies
of the 3-extension of the qutrit case as an illustrative example. Sec. III
elucidates our methodology to compute the reduced density matrix of global
states for a general $k$-extendible state, and underscores our rationale for
dimensionality reduction. Sec.IV shows the comparison of our new algorithm and
traditional one. Concluding insights and discussions are furnished in Sec. V.

##  II qutrit example

Before starting to solve the general problem, we first take a look at $2$
simple examples, $2$ and $3$-extension of qutrit. In fact, these $2$ case
clearly demonstrated why our new algorithm can greatly reduce the size of
searching space. We are going to investigate how many real parameters are
needed to fully describe the global symmetric extended matrix
$\rho_{A\vec{B}}$, which lies in Hilbert space $V=V_{A}\otimes\mathcal{T}$
constituted by part $A$ and $\vec{B}$, with the constrains that
$\operatorname{Tr}_{(AB_{1})^{c}}(\rho_{A\vec{B}})=\rho_{AB}$.

###  II.1 $2$-qutrit

In this case, $\mathcal{T}\equiv V^{(1)}\otimes V^{(2)}$ is constituted by
$2$-qutrit $B_{1}$ and $B_{2}$, where $V^{(1)}$ and $V^{(2)}$ represents
$B_{1}$ and $B_{2}$, respectively. $\mathcal{T}$ is spanned by nine vectors
$\\{|00\rangle,|01\rangle,\cdots,|22\rangle\\}$. According to different
permutation symmetry, $\mathcal{T}$ can be decomposed as $2$ invariant
orthogonal subspace, $6$-dimensional bosonic one $V^{B}$ and $3$-dimensional
fermionic one $V^{F}$. It is clear that, there does not exist any cross term
of bosonic subspace and formionic subspace, therefore we only have to consider
the density matrix $\bar{\rho}_{A\vec{B}}$ supporting on
$\mathrm{End}(V_{A})\otimes\mathrm{End}(V^{B})$ and $\tilde{\rho}_{A\vec{B}}$
supporting on $\mathrm{End}(V_{A})\otimes\mathrm{End}(V^{F})$.

The general form of $\bar{\rho}_{A\vec{B}}$ reads

$\bar{\rho}_{A\vec{B}}=\sum_{\alpha,\beta=1}^{6}\rho_{A}^{(\alpha,\beta)}\otimes\bar{p}_{\alpha,\beta}|\phi^{\alpha}_{\vec{B}}\rangle\langle\
\phi^{\beta}_{\vec{B}}|,$ (2.1)

where $\rho_{A}^{(\alpha,\beta)}\in\mathrm{End}(V_{A})$,
$\bar{p}_{\alpha,\beta}$ is complex number and

$\displaystyle\\{|\phi^{\alpha}_{\vec{B}}\rangle\\}$ $\displaystyle=$
$\displaystyle\left\\{|00\rangle,|11\rangle,|22\rangle,\frac{1}{\sqrt{2}}(|01\rangle+|10\rangle),\right.$
$\displaystyle\left.\frac{1}{\sqrt{2}}(|02\rangle+|20\rangle),\frac{1}{\sqrt{2}}(|12\rangle+|21\rangle),\right\\}.$

The reduced density matrix can be obtained by doing partial trace over $B_{2}$

$\displaystyle
2\times\operatorname{Tr}_{V^{(2)}}(\bar{\rho}_{A\vec{B}})=\sum_{a,b=0}^{2}\bar{M}_{ab}\otimes|a\rangle\langle
b|,$ (2.2)

where $\bar{M}_{ab}$ is given by

$\displaystyle\bar{M}_{00}$ $\displaystyle=$ $\displaystyle
2\bar{p}_{1,1}\rho_{A}^{(1,1)}+\bar{p}_{4,4}\rho_{A}^{(4,4)}+\bar{p}_{5,5}\rho_{A}^{(5,5)},$
$\displaystyle\bar{M}_{11}$ $\displaystyle=$ $\displaystyle
2\bar{p}_{2,2}\rho_{A}^{(2,2)}+\bar{p}_{4,4}\rho_{A}^{(4,4)}+\bar{p}_{6,6}\rho_{A}^{(6,6)},$
$\displaystyle\bar{M}_{22}$ $\displaystyle=$ $\displaystyle
2\bar{p}_{3,3}\rho_{A}^{(3,3)}+\bar{p}_{5,5}\rho_{A}^{(5,5)}+\bar{p}_{6,6}\rho_{A}^{(6,6)},$
$\displaystyle\bar{M}_{01}$ $\displaystyle=$
$\displaystyle{\bar{M}_{10}}^{\dagger}=\sqrt{2}\bar{p}_{4,1}\rho_{A}^{(4,1)}+\sqrt{2}\bar{p}_{2,4}\rho_{A}^{(2,4)}+\bar{p}_{6,5}\rho_{A}^{(6,5)},$
$\displaystyle\bar{M}_{02}$ $\displaystyle=$
$\displaystyle{\bar{M}_{20}}^{\dagger}=\sqrt{2}\bar{p}_{5,1}\rho_{A}^{(5,1)}+\sqrt{2}\bar{p}_{3,5}\rho_{A}^{(3,5)}+\bar{p}_{6,4}\rho_{A}^{(6,4)},$
$\displaystyle\bar{M}_{12}$ $\displaystyle=$
$\displaystyle{\bar{M}_{21}}^{\dagger}=\sqrt{2}\bar{p}_{6,2}\rho_{A}^{(6,2)}+\sqrt{2}\bar{p}_{3,6}\rho_{A}^{(3,6)}+\bar{p}_{5,4}\rho_{A}^{(5,4)}.$

It is noticed that in each term of the RHS in Eq(2.2) does not contain every
$\bar{p}_{\alpha,\beta}$. In fact, the nonzero coefficients before
$\bar{p}_{\alpha,\beta}$ in the term $|a\rangle\langle b|$ are exactly the
nonzero entries of representation matrix $T_{(ab)}$ over this bosonic
invariant subspace.111You may find the representation of $su(3)$ for this case
and the following case in standard textbook on group theory, such as Georgi
and Slansky (1983); Hamermesh (2012).

Similarly, one can write down the general form of $\tilde{\rho}_{A\vec{B}}$
supporting on $\mathrm{End}(V_{A})\otimes\mathrm{End}(V^{F})$

$\tilde{\rho}_{A\vec{B}}=\sum_{\alpha,\beta=1}^{3}\rho_{A}^{(\alpha,\beta)}\otimes\tilde{p}_{\alpha,\beta}|\psi^{\alpha}_{\vec{B}}\rangle\langle\psi^{\beta}_{\vec{B}}|,$
(2.4)

where $\rho_{A}^{(\alpha,\beta)}\in\mathrm{End}(V_{A})$,
$\tilde{p}_{\alpha,\beta}$ is complex number and
$\\{|\psi^{\alpha}_{\vec{B}}\rangle\\}$ is

$\displaystyle\left\\{\frac{1}{\sqrt{2}}(|01\rangle-|10\rangle),\frac{1}{\sqrt{2}}(|02\rangle-|20\rangle),\frac{1}{\sqrt{2}}(|12\rangle-|21\rangle),\right\\}.$

The reduced density matrix can be obtained by doing partial trace over $B_{2}$

$\displaystyle
2\times\operatorname{Tr}_{V^{(2)}}(\tilde{\rho}_{A\vec{B}})=\sum_{a,b=0}^{2}\tilde{M}_{ab}\otimes|a\rangle\langle
b|,$ (2.5)

where $\tilde{M}_{ab}$ is given by

$\displaystyle\tilde{M}_{00}$ $\displaystyle=$ $\displaystyle
2\tilde{p}_{1,1}\rho_{A}^{(1,1)}+\tilde{p}_{2,2}\rho_{A}^{(2,2)},$
$\displaystyle\tilde{M}_{11}$ $\displaystyle=$
$\displaystyle\tilde{p}_{1,1}\rho_{A}^{(1,1)}+\tilde{p}_{3,3}\rho_{A}^{(3,3)},$
$\displaystyle\tilde{M}_{22}$ $\displaystyle=$
$\displaystyle\tilde{p}_{2,2}\rho_{A}^{(2,2)}+\tilde{p}_{3,3}\rho_{A}^{(3,3)},$
$\displaystyle\tilde{M}_{01}$ $\displaystyle=$
$\displaystyle{\tilde{M}_{10}}^{\dagger}=\tilde{p}_{3,2}\rho_{A}^{(3,2)},$
$\displaystyle\tilde{M}_{02}$ $\displaystyle=$
$\displaystyle{\tilde{M}_{20}}^{\dagger}=-\tilde{p}_{3,1}\rho_{A}^{(3,1)},$
$\displaystyle\tilde{M}_{12}$ $\displaystyle=$
$\displaystyle{\tilde{M}_{21}}^{\dagger}=\tilde{p}_{2,1}\rho_{A}^{(2,1)}.$

Taking both $\bar{\rho}_{A\vec{B}}$ and $\tilde{\rho}_{A\vec{B}}$ into
account, much less real parameters is needed: the original algorithm searches
the entire Hilbert space and thus the number of parameters is
$9^{2}d_{A}^{2}$, while usage of permutation symmetry can reduce such number
to $(6^{2}+3^{2})d_{A}^{2}$. It should be stressed that such simplification
comes from the fact that the cross terms between subspaces corresponding to
different permutation symmetry are forbidden.

However, naively usage of symmetry, such as simply symmetrizing the Gell-Mann
matrices over $B_{1}$ and $B_{2}$ has to determine the positive definiteness
of 1 matrix with dimension $(6^{2}+3^{2})d_{A}^{2}$. As a comparison, our
method involves determining the positive definiteness of 2 matrices, whose
dimension are $6^{2}d_{A}^{2}$ and $3^{2}d_{A}^{2}$ respectively.

###  II.2 $3$-qutrit

In this case, $\mathcal{T}\equiv V^{(1)}\otimes V^{(2)}\otimes V^{(3)}$ is
constituted by $3$-qutrit $B_{1}$, $B_{2}$ and $B_{3}$, where $V^{(i)}$
represents $B_{i}$ respectively. Similar as the procedure in the previous
subsection, one can decompose $\mathcal{T}$ as direct sum of subspace
according to different permutation symmetry, and further more, there does not
exist cross term between subspaces corresponding to different permutation
symmetry. The permutation symmetry of $3$-qutrit case is much more complicated
than the $2$-qutrit case. It is easy to verify that there exist a
$10$-dimensional bosonic subspace and a $1$-dimensional fermionic subspace.
Therefore one can solve this problem by imitating previous subsection and
obtain the constrain equations. In this situation, the dimension of searching
space can be reduced from $27^{2}d_{A}^{2}$ to
$(10^{2}+16^{2}+1^{2})d^{2}_{A}$.

However, more room is left in simplification. According to Weyl duality, the
$16$-dimensional subspace can be further decomposed as $2$ orthogonal
$8$-dimensional invariant subspaces $\mathcal{T}^{[2,1]}_{1}$ and
$\mathcal{T}^{[2,1]}_{2}$, and both are loaded with an equivalent $su(3)$
irreducible representation, described by a two row Young diagram
$[2,1]$.222Here
$[\lambda]\equiv\\{\lambda_{1},\lambda_{2},\cdots,\lambda_{n}\\}$ is a
partition of integer $k$, where all $\lambda_{i}$ are integers satisfying
$\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{n}\geq
0,\sum_{i=1}^{n}\lambda_{i}=k$. Such partition is denoted by an $n$-row Young
diagram.

$\mathcal{T}^{[2,1]}_{1}$ and $\mathcal{T}^{[2,1]}_{2}$ are spanned by vectors
$\\{\varphi^{\alpha,(1)}_{\vec{B}}\\}$ and
$\\{\varphi^{\alpha,(2)}_{\vec{B}}\\}$:

$\displaystyle\left\\{\frac{1}{\sqrt{6}}(2|001\rangle-|010\rangle-|100\rangle),\frac{1}{\sqrt{6}}(2|002\rangle-|020\rangle-|200\rangle),\frac{1}{\sqrt{6}}(|011\rangle-|101\rangle-2|110\rangle),\right.$
$\displaystyle\quad\frac{1}{\sqrt{12}}(2|012\rangle-|021\rangle+2|102\rangle-|120\rangle-|201\rangle-|210\rangle),\frac{1}{\sqrt{4}}(|021\rangle-|120\rangle+|201\rangle-|210\rangle),$
$\displaystyle\quad\left.\frac{1}{\sqrt{6}}(|022\rangle+|202\rangle-2|220\rangle),\frac{1}{\sqrt{6}}(2|112\rangle-|121\rangle-|211\rangle),\frac{1}{\sqrt{6}}(|122\rangle+|212\rangle-2|221\rangle)\right\\},$

$\displaystyle\left\\{\frac{1}{\sqrt{2}}(|010\rangle-|100\rangle),\frac{1}{\sqrt{2}}(|020\rangle-|200\rangle),\frac{1}{\sqrt{2}}(|011\rangle-|101\rangle),\right.$
$\displaystyle\quad\frac{1}{\sqrt{4}}(|021\rangle+|120\rangle-|201\rangle-|210\rangle),\frac{1}{\sqrt{12}}(2|012\rangle+|021\rangle-2|102\rangle-|120\rangle-|201\rangle+|210\rangle),$
$\displaystyle\quad\left.\frac{1}{\sqrt{2}}(|022\rangle-|202\rangle),\frac{1}{\sqrt{2}}(|121\rangle-|211\rangle),\frac{1}{\sqrt{2}}(|122\rangle-|212\rangle),\right\\}.$

Under the constrain condition imposed in Eq(1.1), the general form of global
state $\hat{\rho}_{A\vec{B}}$ supporting on
$\mathrm{End}(V_{A})\otimes\mathrm{End}(\mathcal{T}^{[2,1]}_{1}\oplus\mathcal{T}^{[2,1]}_{2})$
must be of the following form:

$\hat{\rho}_{A\vec{B}}=\sum_{\alpha,\beta=1}^{8}\rho_{A}^{(\alpha,\beta)}\otimes\hat{p}_{\alpha,\beta}\left(|\varphi^{\alpha,(1)}_{\vec{B}}\rangle\langle\varphi^{\beta,(1)}_{\vec{B}}|+|\varphi^{\alpha,(2)}_{\vec{B}}\rangle\langle\varphi^{\beta,(2)}_{\vec{B}}|\right),$
(2.7)

The reduced density matrix can be obtained by doing partial trace over $B_{2}$

$\displaystyle\frac{3}{2}\times\operatorname{Tr}_{V^{(2)}}(\hat{\rho}_{A\vec{B}})=\sum_{a,b=0}^{2}\hat{M}_{ab}\otimes|a\rangle\langle
b|,$ (2.8)

where $\tilde{M}_{ab}$ is given by

$\displaystyle\hat{M}_{00}$ $\displaystyle=$ $\displaystyle
2\hat{p}_{1,1}\rho_{A}^{(1,1)}+2\hat{p}_{2,2}\rho_{A}^{(2,2)}+\hat{p}_{1,1}\rho_{A}^{(1,1)}+\hat{p}_{4,4}\rho_{A}^{(4,4)}+p_{5,5}\rho_{A}^{(5,5)}+\hat{p}_{6,6}\rho_{A}^{(6,6)},$
$\displaystyle\hat{M}_{11}$ $\displaystyle=$
$\displaystyle\hat{p}_{1,1}\rho_{A}^{(1,1)}+2\hat{p}_{3,3}\rho_{A}^{(3,3)}+\hat{p}_{4,4}\rho_{A}^{(4,4)}\hat{p}_{5,5}\rho_{A}^{(5,5)}+2\hat{p}_{7,7}\rho_{A}^{(7,7)}+\hat{p}_{8,8}\rho_{A}^{(8,8)},$
$\displaystyle\hat{M}_{22}$ $\displaystyle=$
$\displaystyle\hat{p}_{2,2}\rho_{A}^{(2,2)}+\hat{p}_{4,4}\rho_{A}^{(4,4)}+\hat{p}_{5,5}\rho_{A}^{(5,5)}+2\hat{p}_{6,6}\rho_{A}^{(6,6)}+\hat{p}_{7,7}\rho_{A}^{(7,7)}+2\hat{p}_{8,8}\rho_{A}^{(8,8)},$
$\displaystyle\hat{M}_{01}=\hat{M}_{10}^{\dagger}$ $\displaystyle=$
$\displaystyle-\frac{1}{\sqrt{2}}\hat{p}_{4,1}\rho_{A}^{(4,1)}+\sqrt{\frac{3}{2}}\hat{p}_{5,1}\rho_{A}^{(5,1)}+\hat{p}_{6,2}\rho_{A}^{(6,2)}+\frac{1}{\sqrt{2}}\hat{p}_{8,4}\rho_{A}^{(8,4)}-\sqrt{\frac{3}{2}}\hat{p}_{8,5}\rho_{A}^{(8,5)}-\hat{p}_{7,3}\rho_{A}^{(7,3)},$
$\displaystyle\hat{M}_{02}=\hat{M}_{20}^{\dagger}$ $\displaystyle=$
$\displaystyle\hat{p}_{2,1}\rho_{A}^{(2,1)}+\frac{1}{\sqrt{2}}\hat{p}_{4,3}\rho_{A}^{(4,3)}+\sqrt{\frac{3}{2}}\hat{p}_{5,3}\rho_{A}^{(5,3)}+\frac{1}{\sqrt{2}}\hat{p}_{6,4}\rho_{A}^{(6,4)}+\sqrt{\frac{3}{2}}\hat{p}_{6,5}\rho_{A}^{(6,5)}+\hat{p}_{2,1}\rho_{A}^{(2,1)},$
$\displaystyle\hat{M}_{12}=\hat{M}_{21}^{\dagger}$ $\displaystyle=$
$\displaystyle\hat{p}_{3,1}\rho_{A}^{(3,1)}+\sqrt{2}\hat{p}_{4,2}\rho_{A}^{(4,2)}+\hat{p}_{7,4}\rho_{A}^{(7,4)}+\hat{p}_{8,7}\rho_{A}^{(8,7)}.$

Due to the permutation requirement, the number of real parameters is less than
$(10^{2}+8^{2}+1^{2})d_{A}^{2}$, since some pairs of $\alpha$ and $\beta$ may
contribute nothing when computing the $1$-body reduced density matrix.333BUt
these number can not be set $0$ directly, since they may affect the positive
definiteness. It should be stressed that the simplification comes from not
only the fact that the cross terms between subspaces corresponding to
different permutation symmetry are forbidden, but also arises from the fact
that majority of cross terms within subspaces corresponding to identical
permutation symmetry are also forbidden. It should also be noticed that, via
our method, one can check the positive definiteness of global state by
successively checking the positive definiteness of density matrix
corresponding to different permutation symmetries.

##  III complexity of improved SDP

In this section we are going to give the general form of a global state that
corresponds to the given quantum marginals $\rho_{AB}$.

Consider the symmetric extension problem described in Eq.(1.2). It is required
that the global state $\rho_{AB_{1}\cdots B_{k}}$ is invariant under any
exchange of $B_{i}$ and $B_{j}$, but it does not require that
$\rho_{AB_{1}\cdots B_{k}}$ must support on a subspace with specific
permutation symmetry. e.g. for a $2$-symmetric extendible state, its extension
can be bosonic, which supports on the symmetric subspace only, or fermionic,
whose support only resides on the antisymmetric subspace, or more generally,
can be a mixture of both.

Consider a Hilbert space $\mathcal{T}=\bigotimes_{i=1}^{k}V^{(i)}$ constituted
by $k$-qudit $B_{1},B_{2},\cdots,B_{k}$, whose computational basis is
$\left\\{\Phi_{i_{1},i_{2},\cdots,i_{k}}\equiv|i_{1},i_{2},\cdots,i_{k}\rangle\right\\}$,
where $i_{1},i_{2},\cdots,i_{k}=0,1,\cdots,d-1$.

Each subsystem $V^{(i)}$ is invariant under $SU(d)$ ’rotation’, and transforms
according to the $d$ dimensional fundamental irreducible representation
$D^{[1]}$, which corresponds to the Young diagram $[1]$. 444this is the $1$
block Young diagram 1 ( ).

Therefore the Lie algebra $su(d)$, which is constituted by $3$ series of zero
trace hermitian matrices and describes the infinite small rotation of $SU(d)$,
has the following matrix forms on each identical $V^{(j)}$, if we set
$|i\rangle$ to be the natural basis,

$\displaystyle\left(T^{(1)}_{mn}\right)_{st}$ $\displaystyle=$
$\displaystyle\frac{1}{2}(\delta_{ms}\delta_{nt}+\delta_{ns}\delta_{mt}),$
$\displaystyle\left(T^{(2)}_{mn}\right)_{st}$ $\displaystyle=$
$\displaystyle\frac{-i}{2}(\delta_{ms}\delta_{nt}+\delta_{ns}\delta_{mt}),$
$\displaystyle\left(T^{(3)}_{p}\right)_{st}$ $\displaystyle=$
$\displaystyle\left\\{\begin{tabular}[]{l
l}$\delta_{st}[2(p+1)p]^{-\frac{1}{2}}$,&$s<p$,\\\
$-\delta_{st}[p/(2p+2)]^{\frac{1}{2}}$,&$s=p$,\\\
$0$,&$s>p$,\end{tabular}\right.,$

where $m<n,$ and $1\leq p\leq d-1$. Taking the global phase into account, one
should also include the identity matrix. Therefore one can obtain a new basis
for Lie algebra $u(d)$ by

$\\{T_{ab}|\left(T_{ab}\right)_{st}=\delta_{as}\delta_{bt},0\leq a,b\leq
d-1\\}.$

$\mathcal{T}$ is also invariant under the global $U(d)$ transformation , whose
corresponding Lie algebra is given by
$\\{\mathbf{T}_{ab}|\mathbf{T}_{ab}=\sum_{i}T^{(i)}_{ab}\\}$.555Here
$T^{(i)}_{ab}$ denotes that the $i$-th subsystem transforms according to
$T_{ab}$ while others according to the identity operator. $\mathcal{T}$
transforms under representation $\otimes^{k}[1]$, which is not irreducible,
but can be decomposed as direct sum of a series of irreducible
representations,

$\displaystyle\bigotimes\nolimits^{k}D^{[1]}=\bigoplus_{[\lambda]}m_{[\lambda]}D^{[\lambda]},$
(3.2)

where $m_{[\lambda]}$ is the multiplicity of irreducible representation
$D^{[\lambda]}$. This is equivalent to say that $\mathcal{T}$ can be
partitioned as direct sum of subspaces.666Please be notified that, subspaces
corresponding to different Young diagram are orthogonal to each other, while
those corresponding to same Young diagram are not. However, it is guaranteed
that the intersection of such $2$ different subspaces is zero.

$\mathcal{T}=\bigoplus_{[\lambda]}m_{[\lambda]}\mathcal{T}^{[\lambda]}.$ (3.3)

It can be easily manifested that, such $\mathcal{T}^{[\lambda]}$ has
particular permutation symmetry described by Young diagram $[\lambda]$, and
the multiplicity $m_{[\lambda]}$ equals to the dimension of irreducible
representation of $S_{k}$ corresponding to the identical Young diagram
$[\lambda]$, which gives an equation

$d^{k}=\sum_{[\lambda]}m_{[\lambda]}D^{[\lambda]}.$ (3.4)

Two irreducible representation spaces $\mathcal{T}^{[\lambda]}_{\mu}$ and
$\mathcal{T}^{[\lambda]}_{\nu}$ corresponding to same Young diagram but
different Young tableaus are orthogonal to each other. Although there might
probably be multiplicity in some weight subspace for a general irreducible
subspace, one can uniquely label a vector within arbitrary given irreducible
subspace by its weight $\vec{\omega}$ in $su(d)$ and the subgroup chain
$su(d)\supset su(d-1)\supset\cdots\supset su(2)$ Gelfand (1988). Thus one can
safely use weight $\vec{\omega}$ to label different states inside an
irreducible subspace $\mathcal{T}^{[\lambda]}_{\mu}$. Therefore,
$\\{|[\lambda],\mu,\vec{\omega}\rangle\\}$ labels a complete basis of
$\mathcal{T}$ one by one, where $[\lambda]$ tells inequivalent $su(d)$
representations while $\mu$ differentiate equivalent ones. They together
determine an orthogonal irreducible subspace, and $\vec{\omega}$ labels every
different vectors inside.

On the other hand, $\\{|[\lambda],\mu,\omega\rangle\\}$ can be interpreted in
another way: $\vec{\omega}$ describes the weight, $[\lambda]$ tells
inequivalent $S_{k}$ representations, thus these two parameter differentiate
orthogonal invariant subspaces, while $\mu$ labels vectors inside. From now on
we shall use $|\vec{\omega}^{[\lambda]}_{\mu}\rangle$ short for
$|\vec{\omega},[\lambda],\mu\rangle$.

Any matrix $\rho_{AB_{1}B_{2}\cdots
B_{n}}\in\mathrm{End}(V_{A})\otimes\mathrm{End}(\mathcal{T})$ can be expressed
as

$\displaystyle\rho_{AB_{1}B_{2}\cdots B_{k}}$ $\displaystyle=$
$\displaystyle\sum_{\alpha,\alpha^{\prime}}\sum_{[\lambda],[\lambda^{\prime}]}\sum_{\mu,\mu^{\prime}}\sum_{\vec{\omega},\vec{\omega^{\prime}}}|\psi^{\alpha}_{\vec{\omega},[\lambda],\mu}\rangle\langle\psi^{\alpha^{\prime}}_{\vec{\omega^{\prime}},[\lambda^{\prime}],\mu^{\prime}}|$
$\displaystyle\qquad\otimes|\vec{\omega}^{[\lambda]}_{\mu}\rangle\langle\vec{\omega^{\prime}}^{[\lambda^{\prime}]}_{\mu^{\prime}}|,$

where $|\psi^{\alpha}_{\vec{\omega},[\lambda],\mu}\rangle$ are non-normalized
state in $V_{A}$ and $\alpha$ label different states in $V_{A}$.

Insert Eq.(III) into Eq.(1.2). $\forall\pi\in S_{k}$ we get a series of
constrains for $\rho_{AB_{1}B_{2}\cdots B_{k}}$:

$\displaystyle\quad\forall[\lambda],[\lambda^{\prime}]\vec{\omega},\vec{\omega^{\prime}}\textrm{
and }\mu,\mu^{\prime},$
$\displaystyle\sum_{\alpha,\alpha^{\prime}}|\psi^{\alpha}_{\vec{\omega},[\lambda],\mu}\rangle\langle\psi^{\alpha^{\prime}}_{\vec{\omega^{\prime}},[\lambda^{\prime}],\mu^{\prime}}|\sum_{\nu,\nu^{\prime}}\mathcal{A}(\pi)^{[\lambda]}_{\mu,\nu}\mathcal{A}(\pi)^{[\lambda^{\prime}]*}_{\nu^{\prime},\mu^{\prime}}|\vec{\omega}^{[\lambda]}_{\nu}\rangle\langle\vec{\omega^{\prime}}^{[\lambda^{\prime}]}_{\nu^{\prime}}|$
$\displaystyle\qquad=\sum_{\alpha,\alpha^{\prime}}|\psi^{\alpha}_{\vec{\omega},[\lambda],\mu}\rangle\langle\psi^{\alpha^{\prime}}_{\vec{\omega^{\prime}},[\lambda^{\prime}],\mu^{\prime}}||\vec{\omega}^{[\lambda]}_{\mu}\rangle\langle\vec{\omega^{\prime}}^{[\lambda^{\prime}]}_{\mu^{\prime}}|,\qquad$
(3.6)

where $\mathcal{A}^{[\lambda]}$ and $\mathcal{A}^{[\lambda^{\prime}]}$ are
irreducible representations of permutation group $S_{k}$.

Define matrix

$\displaystyle
M(\vec{\omega},\vec{\omega^{\prime}},[\lambda],[\lambda^{\prime}])$ (3.7)
$\displaystyle\equiv$
$\displaystyle\sum_{\mu,\mu^{\prime}}M(\vec{\omega},\vec{\omega^{\prime}},[\lambda],[\lambda^{\prime}])_{\mu\mu^{\prime}}|\vec{\omega}^{[\lambda]}_{\mu}\rangle\langle\vec{\omega^{\prime}}^{[\lambda^{\prime}]}_{\mu^{\prime}}|,$

where

$M(\vec{\omega},\vec{\omega^{\prime}},[\lambda],[\lambda^{\prime}])_{\mu\mu^{\prime}}\equiv\sum_{\alpha,\alpha^{\prime}}|\psi^{\alpha}_{\vec{\omega},[\lambda],\mu}\rangle\langle\psi^{\alpha^{\prime}}_{\vec{\omega^{\prime}},[\lambda^{\prime}],\mu^{\prime}}|,$
(3.8)

thus $\forall\pi\in S_{k}$

$\displaystyle\mathcal{A}^{[\lambda]}(\pi)M(\vec{\omega},\vec{\omega^{\prime}},[\lambda],[\lambda^{\prime}])\mathcal{A}^{[\lambda^{\prime}]}(\pi)^{\dagger}$
$\displaystyle=$ $\displaystyle
M(\vec{\omega},\vec{\omega^{\prime}},[\lambda],[\lambda^{\prime}]).$

Schur’s lemma guarantee that,

  * a.

when $[\lambda]\neq[\lambda^{\prime}]$, $M=0$;

  * b.

when $[\lambda]=[\lambda^{\prime}]$, $M$ is invertible.

Choose $|\vec{\omega}_{\mu}^{[\lambda]}\rangle$ carefully such that the
representation $\mathcal{A}^{[\lambda]}$ are identical, not just an isomorphic
matrix, for different weight $\omega$. Then all
$M(\vec{\omega},\vec{\omega^{\prime}},[\lambda],[\lambda])$ can be
proportional to the corresponding identity matrix. Therefore, one could
eliminate majority of cross terms and restrict $\rho_{AB_{1}B_{2}\cdots
B_{k}}$ to

$\displaystyle\rho_{AB_{1}B_{2}\cdots B_{k}}$ $\displaystyle=$
$\displaystyle\sum_{[\lambda]}\sum_{\vec{\omega},\vec{\omega^{\prime}}}f([\lambda],\vec{\omega},\vec{\omega^{\prime}})\sigma([\lambda],\vec{\omega},\vec{\omega^{\prime}})$
(3.10)
$\displaystyle\otimes\sum_{\mu}|\vec{\omega}^{[\lambda]}_{\mu}\rangle\langle\vec{\omega}^{\prime[\lambda]}_{\mu}|,$

where $f([\lambda],\vec{\omega},\vec{\omega^{\prime}})$ is the coefficient and
$\sigma([\lambda],\vec{\omega},\vec{\omega^{\prime}})\in\mathrm{End}(V_{A})$(do
not have to be a density matrix!), both of which correspond to $S_{k}$
irreducible representation described by Young diagram $[\lambda]$ and
different weight $\vec{\omega}$ and $\vec{\omega^{\prime}}$.

Our next task is to determine the RDM of global state given by Eq.(3.10). For
every given $[\lambda],\vec{\omega}$ and $\vec{\omega^{\prime}}$, one could
temporally ignore system $A$ and concentrate on group
$\\{B_{1},B_{2},\cdots,B_{k}\\}$,

$\displaystyle\sum_{i,j=0}^{d-1}B_{ij}|i\rangle\langle j|$ $\displaystyle=$
$\displaystyle\operatorname{Tr}_{B_{1}^{c}}\left(\sum_{\mu}|\vec{\omega}^{[\lambda]}_{\mu}\rangle\langle\vec{\omega}^{\prime[\lambda]}_{\mu}|\right)$
$\displaystyle=$ $\displaystyle\sum_{i,j=0}^{d-1}|i\rangle\langle
j|\operatorname{Tr}\left(T^{(1)}_{ji}\sum_{\mu}|\vec{\omega}^{[\lambda]}_{\mu}\rangle\langle\vec{\omega}^{\prime[\lambda]}_{\mu}|\right)$
$\displaystyle=$ $\displaystyle\sum_{i,j=0}^{d-1}|i\rangle\langle
j|\operatorname{Tr}\left(\frac{1}{k}\mathbf{T}_{ji}\sum_{\mu}|\vec{\omega}^{[\lambda]}_{\mu}\rangle\langle\vec{\omega}^{\prime[\lambda]}_{\mu}|\right)$
$\displaystyle=$ $\displaystyle\sum_{i,j=0}^{d-1}|i\rangle\langle
j|\left(\frac{m_{[\lambda]}}{k}\langle\vec{\omega}^{\prime[\lambda]}|\mathbf{T}_{ji}|\vec{\omega}^{[\lambda]}\rangle\right),$

where
$\langle\vec{\omega}^{\prime[\lambda]}|\mathbf{T}_{ji}|\vec{\omega}^{[\lambda]}\rangle$
is exactly the matrix element of irreducible representation corresponding to
Young diagram $[\lambda]$ for generator $T_{ji}$ in Lie algebra $u(d)$.777Do
not worry about this part, the general matrix form of $\mathbf{T}_{ji}$ in
irreducible representation $D^{[\lambda]}$ of $u(d)$ have been calculated by
mathematicians and you can refer to Gelfand (1988). Taking subsystem $A$ into
account, one can obtain

$\displaystyle\operatorname{Tr}_{(AB_{1})^{c}}\left(\rho_{AB_{1}B_{2}\cdots
B_{k}}\right)$ $\displaystyle=$
$\displaystyle\sum_{[\lambda]}\sum_{m,n=0}^{d_{A}-1}\sum_{i,j=0}^{d-1}|m\rangle\langle
n|\otimes|i\rangle\langle j|$
$\displaystyle\times\sum_{\vec{\omega},\vec{\omega}^{\prime}}\sigma([\lambda],\vec{\omega},\vec{\omega^{\prime}})_{mn}\frac{m_{[\lambda]}}{k}\langle\vec{\omega}^{\prime[\lambda]}|\mathbf{T}_{ji}|\vec{\omega}^{[\lambda]}\rangle
f([\lambda],\vec{\omega},\vec{\omega^{\prime}}).$

For every given $[\lambda]$, the number of different values for $\vec{\omega}$
and $\vec{\omega^{\prime}}$ is just the dimension of $u(d)$ irreducible
representation $D^{[\lambda]}$. Therefore, ignoring the size of subsystem $A$,
the size of searching space in dealing with symmetric extension is given by

$\sum\left(D^{[\lambda]}\right)^{2}=\binom{d^{2}-1+k}{k}<d^{2k},$ (3.13)

where the summation runs over all possible proper Young diagrams. One may
conclude that, the dimension of entire searching space grows not faster than
$O(k^{d^{2}})$, which is significantly smaller than the original $O(d^{2k})$,
therefore the efficiency of SDP could be greatly improved when dealing with
symmetric extension problems.

To guarantee the positive definiteness of solved global matrix, one can test
whether the density matrix corresponding to different permutation is positive
definite respectively, and hence each testing need much less resource.

To investigate the amount of the resource needed for each single testing, one
should focus on the growth rate of $D^{[\lambda]}$ and $m_{[\lambda]}$. The
asymptotic behavior of the upper bound of $D^{[\lambda]}$ is given by

$\prod_{m=1}^{d-1}\frac{1}{(m)!}\left(1+\frac{2k}{d(d+1)}\right)^{\frac{d(d-1)}{2}},$
(3.14)

which corresponds to the irreducible representation that satisfies
$\lambda_{i}-\lambda_{i+1}\approx 2k/d(d-1)$ Fulton (1997). For a given $k$,
the number of different valid Young diagrams whose row is less than or equal
to $d$ is hard to compute analytically, but for sufficient large $k$, the
asymptotic value is $\frac{1}{d!}\binom{k+d-1}{k}$. 888To find a partition(not
necessarily a partition corresponds to valid Young diagram!) that satisfies
$\sum_{i}^{k}\lambda_{i}=k$ is equivalent to insert $d-1$ separators between a
line of $k$ balls, which reads $\binom{k+d-1}{k}$. Since some $\lambda_{i}$s
might be identical, the number of valid different Young diagrams should be
less than $\frac{1}{d!}\binom{k+d-1}{k}$, but when $k$ is sufficient large,
such odd approaches to $0$, so the asymptotic number of valid Young diagrams
is given by $\frac{1}{d!}\binom{k+d-1}{k}$.

##  IV Numerical results

First, we apply our algorithm on the famous bipartite Werner state
$\rho_{W,d}\left(\alpha\right)\in\mathcal{H}_{d}\otimes\mathcal{H}_{d}$

$\rho_{W,d}\left(\alpha\right)=\frac{1}{d^{2}-d\alpha}I-\frac{\alpha}{d^{2}-d\alpha}\sum_{ij}\left|ij\right\rangle\left\langle
ji\right|,\;\alpha\in\left[-1,1\right].$

Previous work Johnson and Viola (2013) proved that the Werner state is
$(1,k)$-extendible for $\alpha\in[-1,\frac{k+d^{2}-d}{kd+d-1}]$. As $k$ goes
to infinity, it gives the separable Werner state
$\alpha\in\left[-1,\frac{1}{d}\right]$. To obtain such a $(1,k)$-extendible
boundary $\alpha_{k}^{*}$, one can solve the following semi-definite
programming

$\displaystyle\max\;c,$ $\displaystyle s.t.$
$\displaystyle\begin{cases}\rho_{AB_{1}\cdots B_{k}}\succeq 0,\\\
\left(\mathbb{1}^{A}\otimes P_{ij}\right)\rho_{AB_{1}\cdots
B_{k}}\left(\mathbb{1}^{A}\otimes P_{ij}\right)=\rho_{AB_{1}\cdots B_{k}},\\\
\operatorname{Tr}_{B_{1}^{c}}\left(\rho_{AB_{1}\cdots
B_{k}}\right)=\left(1-c\right)\rho_{o}+c\rho_{W,d}(1),\end{cases}$

with $\rho_{0}$ denotes the maximally mixed state999As semi-definite
programming requires linear or affine equation constraint, we convert the non-
linear expression $\alpha$ in Werner state into a linear interpolation
$(1-c)\rho_{0}+c\rho_{W,d}(1)$ used in optimization., and The boundary can be
calculated from the optimal value $\alpha_{k}^{*}=\frac{c^{*}d}{c^{*}+d-1}$.

$(d,k)$ | QETLAB (s) | irrep (s) | $\alpha_{k}^{*}$
---|---|---|---
$(2,8)$ | 0.19 | 0.16 | 0.588
$(2,10)$ | 12.60 | 0.16 | 0.571
$(2,16)$ | - | 0.32 | 0.545
$(2,32)$ | - | 3.18 | 0.523
$(2,32)$ | - | 51.96 | 0.512
$(3,3)$ | 0.62 | 0.51 | 0.818
$(3,4)$ | 7.96 | 2.38 | 0.714
$(3,5)$ | - | 11.56 | 0.647
$(3,6)$ | - | 55.60 | 0.6
Table 1:  Time usage for calculating the Werner $(1,k)$-extendible boundary.
The dashed line “-” indicates the optimization failed due to memory limitation
or intolerable time usage.

The results are shown in TABLE 1. We compare the time required with the
software QETLAB Johnston  _et al._ (2015), a widely-used MATLAB package in
quantum information community. The benchmark is performed on a standard
laptop, AMD R7-5800H, 16 CPU cores (hyperthread enabled), 16GB memory and our
algorithm is implemented in CVXPY package Diamond and Boyd (2016) with MOSEK
solver ApS (2023). The solved boundary $\alpha_{k}^{*}$ is within $10^{-8}$
absolute error compared with the analytical results. From the results, A
significant speedup can be observed and a much larger $k$-extension problem
can be handled for our algorithm.

We explicitly calculate the dimension of searching space and the number of
parameters required to be tested for positive definiteness, which demonstrate
the efficiency of our algorithms, as shown in TABLE 2. 101010Our algorithm
needs to undergo multiple different positive-definiteness tests, where each
different Young diagram corresponds to its own test, but each individual test
involves significantly small matrix, and hence the efficiency will be
improved.

$(d,k)$ | #searching space (QETLAB,irrep) | #positive definiteness (QETLAB,irrep)
---|---|---
$(3,3)$ | $(729,165)$ | $(729,10^{2}+8^{2}+1^{2})$
$(3,4)$ | $(6561,495)$ | $(6561,15^{2}+15^{2}+6^{2}+3^{2})$
$(3,5)$ | $(59049,1287)$ | $(59049,21^{2}+24^{2}+15^{2}+6^{2}+3^{2})$
$(3,6)$ | $(531441,3003)$ | $(531441,28^{2}+35^{2}+27^{2}+10^{2}+10^{2}+8^{2}+1^{2})$
$(4,3)$ | $(4096,816)$ | $(4096,20^{2}+20^{2}+4^{2})$
$(4,4)$ | $(65536,3876)$ | $(65536,35^{2}+45^{2}+20^{2}+15^{2}+1^{2})$
$(4,5)$ | $(1048576,15504)$ | $(1048576,56^{2}+84^{2}+60^{2}+36^{2}+20^{2}+4^{2})$
Table 2:  Dimensions and number of parameters needed in positive definiteness.

##  V discussion

The complexity of our new algorithm for dealing with k-symmetric extensions of
quantum states is $O(k^{d^{2}})$, which is an improvement over the original
algorithm with $O(d^{2k})$ complexity. However, it is important to note that
the complexity of detecting entanglement is a QMA problem, which means that it
is generally considered to be computationally hard. Although our new algorithm
reduces the computational complexity of the problem, it does _not_ change the
fundamental difficulty of detecting entanglement. This is due to the fact that
the size of the input of this problem is given by $O(\log k,d)$, and hence the
resources needed in our algorithm still grows exponentially relative to the
input. Therefore, while our algorithm presents some advance, it does not
contradict the known fact that detecting entanglement is a QMA problem. The
challenge of detecting entanglement remains an important area of research,
with many open questions and opportunities for new breakthroughs.

## Acknowledgments

The authors would like to thank for Ruan Dong, Huang Huajun, Huang Shilin for
help discussion. Y-N.Li is supported by National Natural Science Foundation of
China under Grant No. 12005295 S-Y.Hou is supported by National Natural
Science Foundation of China under Grant No. 12105195. C.Zhang, Z-P.Wu, and
B.Zeng are supported by GRF (grant no. 16305121).

## References

  * Horodecki  _et al._ (2009) R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, Rev. Mod. Phys. 81, 865 (2009).
  * Bennett and Wiesner (1992) C. H. Bennett and S. J. Wiesner, Phys. Rev. Lett. 69, 2881 (1992).
  * Nielsen and Chuang (2010) M. A. Nielsen and I. L. Chuang,  _Quantum computation and quantum information_ (Cambridge university press, 2010).
  * Klyachko (2006) A. A. Klyachko, J. Phys.: Conf. Ser. 36, 72 (2006).
  * Chen  _et al._ (2014) J. Chen, Z. Ji, D. Kribs, N. Lütkenhaus, and B. Zeng, Phys. Rev. A 90, 032318 (2014).
  * Coleman (1963) A. J. Coleman, Rev. Mod. Phys. 35, 668 (1963).
  * Erdahl (1972) R. M. Erdahl, J. Math. Phys. 13, 1608 (1972).
  * Navascués  _et al._ (2009) M. Navascués, M. Owari, and M. B. Plenio, Physical Review A 80, 052306 (2009).
  * Brandão  _et al._ (2011) F. G. Brandão, M. Christandl, and J. Yard, in  _Proceedings of the forty-third annual ACM symposium on Theory of computing_ (ACM, 2011) pp. 343–352.
  * Johnston (2014) N. Johnston, “Entanglement detection,” (2014).
  * Vandenberghe and Boyd (1996) L. Vandenberghe and S. Boyd, SIAM review 38, 49 (1996).
  * Doherty  _et al._ (2004) A. C. Doherty, P. A. Parrilo, and F. M. Spedalieri, Physical Review A 69, 022308 (2004).
  * Georgi and Slansky (1983) H. Georgi and R. Slansky, “Lie algebras in particle physics,” (1983).
  * Hamermesh (2012) M. Hamermesh,  _Group theory and its application to physical problems_ (Courier Corporation, 2012).
  * Gelfand (1988) I. M. Gelfand,  _Collected Papers II_ , Vol. 2 (Springer Science & Business Media, 1988).
  * Fulton (1997) W. Fulton,  _Young tableaux: with applications to representation theory and geometry_ , 35 (Cambridge University Press, 1997).
  * Johnson and Viola (2013) P. D. Johnson and L. Viola, Physical Review A 88 (2013), 10.1103/physreva.88.032323.
  * Johnston  _et al._ (2015) N. Johnston, A. Cosentino, and V. Russo, “Qetlab: Qetlab v0.7,”  (2015).
  * Diamond and Boyd (2016) S. Diamond and S. Boyd, Journal of Machine Learning Research 17, 1 (2016).
  * ApS (2023) M. ApS,  _MOSEK Optimizer API for Python 10.1.11_ (2023).