* [44] A. Evans, “Liquidity Provider Returns in Geometric Mean Markets,” _Cryptoeconomic Systems_ , vol. 1, no. 2, p. 30, Oct. 2021. [Online]. Available: https://cryptoeconomicsystems.pubpub.org/pub/evans-g3m-returns/release/4
  * [45] PancakeSwap Docs, “PancakeSwap Intro,” 2023. [Online]. Available: https://docs.pancakeswap.finance/
  * [46] Sushi Docs, “Sushi: Be a Crypto Chef with Sushi,” 2023. [Online]. Available: https://docs.sushi.com/pdf/whitepaper.pdf
  * [47] J. C. Schlegel, M. Kwaśnicki, and A. Mamageishvili, “Axioms for Constant Function Market Makers,” Rochester, NY, Nov. 2022. [Online]. Available: https://papers.ssrn.com/abstract=4290001
  * [48] D. Engel and M. Herlihy, “Composing networks of automated market makers,” in _Proceedings of the 3rd ACM Conference on Advances in Financial Technologies_ , ser. AFT ’21. New York, NY, USA: Association for Computing Machinery, Nov. 2021, pp. 15–28. [Online]. Available: https://dl.acm.org/doi/10.1145/3479722.3480987
  * [49] WooFi, “WooFi Dev Docs,” 2023. [Online]. Available: https://learn.woo.org/v/woofi-dev-docs/
  * [50] E. Meyer, I. M. Welpe, and P. G. Sandner, “Decentralized Finance—A Systematic Literature Review and Research Directions,” Social Science Research Network, Rochester, NY, SSRN Scholarly Paper ID 4016497, Nov. 2021. [Online]. Available: https://papers.ssrn.com/abstract=4016497
  * [51] P. Schueffel, “DeFi: Decentralized Finance - An Introduction and Overview,” _Journal of Innovation Management_ , vol. 9, no. 3, pp. I–XI, Nov. 2021, number: 3. [Online]. Available: https://journalengineering.fe.up.pt/index.php/jim/article/view/2183-0606_009-003_0001
  * [52] M. Egorov, “StableSwap - eﬃcient mechanism for Stablecoin liquidity,” 2019. [Online]. Available: https://berkeley-defi.github.io/assets/material/StableSwap.pdf
  * [53] ——, “Automatic market-making with dynamic peg,” 2021. [Online]. Available: https://classic.curve.fi/files/crypto-pools-paper.pdf
  * [54] Rarity Beyond, “What are NFT Automatic Market Makers (AMMs),” 10 2022. [Online]. Available: https://medium.com/the-brr/what-are-nft-automatic-market-makers-amms-82f18eedbb63
  * [55] J. Fountain and G. W. Harrison, “What do prediction markets predict?” _Applied Economics Letters_ , vol. 18, no. 3, p. 12, Feb. 2011. [Online]. Available: https://doi.org/10.1080/13504850903559575
  * [56] Y. Wang, “Prediction Markets, Automated Market Makers, and Decentralized Finance (DeFi),” in _Mathematical Research for Blockchain Economy_ , ser. Lecture Notes in Operations Research, P. Pardalos, I. Kotsireas, Y. Guo, and W. Knottenbelt, Eds. Cham: Springer International Publishing, 2023, pp. 213–231.
  * [57] J. Peterson, J. Krug, M. Zoltu, A. K. Williams, and S. Alexander, “Augur: a decentralized oracle and prediction market platform,” 2018, arXiv:1501.01042 [cs]. [Online]. Available: http://arxiv.org/abs/1501.01042
  * [58] A. Carvalho, “A permissioned blockchain-based implementation of LMSR prediction markets,” _Decision Support Systems_ , vol. 130, p. 113228, Mar. 2020. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S016792361930257X
  * [59] Zeitgeist Docs, “Prediction Markets | Zeitgeist Documentation,” Sep. 2022. [Online]. Available: https://docs.zeitgeist.pm/docs/learn/prediction-markets
  * [60] S. d. l. Rouviere, “Introducing Curation Markets: Trade Popularity of Memes & Information (with code)!” medium.com, Aug. 2019. [Online]. Available: https://medium.com/@simondlr/introducing-curation-markets-trade-popularity-of-memes-information-with-code-70bf6fed9881
  * [61] The Graph, “The Graph: Curating,” 2023. [Online]. Available: https://thegraph.com/
  * [62] Ocean Protocol Foundation and BigChainDB GmbH, “Ocean Protocol: Tools for the Web3 Data Economy,” Dec. 2020. [Online]. Available: https://oceanprotocol.com/tech-whitepaper.pdf
  * [63] G. Fenu, L. Marchesi, M. Marchesi, and R. Tonelli, “The ICO phenomenon and its relationships with ethereum smart contract environment,” in _2018 International Workshop on Blockchain Oriented Software Engineering (IWBOSE)_. USA: IEEE Xplore, Mar. 2018, pp. 26–32.
  * [64] X. Zhao, Z. Chen, X. Chen, Y. Wang, and C. Tang, “The DAO attack paradoxes in propositional logic,” pp. 1743–1746, Nov. 2017.
  * [65] T. Simpson, H. Sheikh, T. Hain, T. Rønnow, and J. Ward, “Fetch Technical Introduction,” 2019.
  * [66] ICODrops, “Ethereum (ETH) - All information about Ethereum ICO (Token Sale),” Oct. 2018, section: Ended ICO. [Online]. Available: https://icodrops.com/ethereum/
  * [67] ——, “Tezos (XTZ) - All information about Tezos ICO (Token Sale),” Dec. 2017, section: Ended ICO. [Online]. Available: https://icodrops.com/tezos/
  * [68] B. G. Malkiel, “The Efficient Market Hypothesis and Its Critics,” _Journal of Economic Perspectives_ , vol. 17, no. 1, pp. 59–82, Mar. 2003. [Online]. Available: https://www.aeaweb.org/articles?id=10.1257/089533003321164958
  * [69] E. F. Fama, “Efficient Capital Markets: A Review of Theory and Empirical Work,” _The Journal of Finance_ , vol. 25, no. 2, pp. 383–417, 1970, publisher: [American Finance Association, Wiley]. [Online]. Available: https://www.jstor.org/stable/2325486
  * [70] A. S. Kyle, “Continuous Auctions and Insider Trading,” _Econometrica_ , vol. 53, no. 6, pp. 1315–1335, 1985, publisher: [Wiley, Econometric Society]. [Online]. Available: https://www.jstor.org/stable/1913210
  * [71] M. L. Hayenga, “The concept of a thin market,” Mar. 1978. [Online]. Available: https://ageconsearch.umn.edu/record/303068
  * [72] J. Xu and B. Livshits, “The Anatomy of a Cryptocurrency {Pump-and-Dump} Scheme,” pp. 1609–1625, 2019. [Online]. Available: https://www.usenix.org/conference/usenixsecurity19/presentation/xu-jiahua
  * [73] T. Li, D. Shin, and B. Wang, “Cryptocurrency Pump-and-Dump Schemes,” Rochester, NY, Feb. 2021. [Online]. Available: https://papers.ssrn.com/abstract=3267041
  * [74] J. Kamps and B. Kleinberg, “To the moon: defining and detecting cryptocurrency pump-and-dumps,” _Crime Science_ , vol. 7, no. 1, p. 18, Nov. 2018. [Online]. Available: https://doi.org/10.1186/s40163-018-0093-5
  * [75] J. M. Corbin and A. L. Strauss, _Basics of Qualitative Research: Techniques and Procedures for Developing Grounded Theory_ , 4th ed. Los Angeles, CA, USA: SAGE Publications, 2015.
  * [76] A. L. Strauss and J. M. Corbin, _Grounded theory in practice_. Thousand Oaks: Sage Publications, 1997.
  * [77] J. Milionis, C. C. Moallemi, T. Roughgarden, and A. L. Zhang, “Automated Market Making and Loss-Versus-Rebalancing,” Sep. 2022, arXiv:2208.06046 [math, q-fin]. [Online]. Available: http://arxiv.org/abs/2208.06046
  * [78] D. Churiwala and B. Krishnamachari, “QLAMMP: A Q-Learning Agent for Optimizing Fees on Automated Market Making Protocols,” Nov. 2022, arXiv:2211.14977 [cs, q-fin]. [Online]. Available: http://arxiv.org/abs/2211.14977
  * [79] S. Fan, T. Min, X. Wu, and C. Wei, “Towards understanding governance tokens in liquidity mining: a case study of decentralized exchanges,” _World Wide Web_ , vol. 26, no. 1, p. 20, Jul. 2022. [Online]. Available: https://doi.org/10.1007/s11280-022-01077-4
  * [80] A. Cartea, F. Drissi, and M. Monga, “Decentralised Finance and Automated Market Making: Execution and Speculation,” Rochester, NY, Jun. 2022. [Online]. Available: https://papers.ssrn.com/abstract=4144743
  * [81] T. Bitterli and F. Schär, “Decentralized Exchanges: The Profitability Frontier of Constant Product Market Makers,” Feb. 2023, arXiv:2302.05219 [q-fin]. [Online]. Available: http://arxiv.org/abs/2302.05219
  * [82] P. O’Neill, “Can Markets be Fully Automated? Evidence From an “Automated Market Maker”,” _Financial Innovation_ , vol. 8, no. 20, p. 48, 2021.
  * [83] A. Othman, D. M. Pennock, D. M. Reeves, and T. Sandholm, “A practical liquidity-sensitive automated market maker,” _ACM Transactions on Economics and Computation_ , vol. 1, no. 3, pp. 1–25, 2013. [Online]. Available: https://dl.acm.org/doi/10.1145/2509413.2509414
  * [84] A. Khakhar and X. Chen, “Delta Hedging Liquidity Positions on Automated Market Makers,” Dec. 2022, arXiv:2208.03318 [cs, q-fin]. [Online]. Available: http://arxiv.org/abs/2208.03318
  * [85] A. Hayden, N. Zinsmeister, S. Moody, R. Keefer, and D. Robinson, “Uniswap v3 Core,” 2021. [Online]. Available: https://uniswap.org/whitepaper-v3.pdf
  * [86] T. Hulsmans and A. Radulescu, “Dynamic Liquidity Concentration with an Oracle Supplied Price and Implied Volatility,” 2021.
  * [87] S. Foley, P. O’Neill, and T. J. Putniņš, “A Better Market Design? Applying ‘Automated Market Makers’ to Traditional Financial Markets,” Rochester, NY, Jun. 2023. [Online]. Available: https://papers.ssrn.com/abstract=4459924
  * [88] D. Z. Zanger, “G3Ms:Generalized Mean Market Makers,” Aug. 2022, arXiv:2208.07305 [q-fin]. [Online]. Available: http://arxiv.org/abs/2208.07305
  * [89] A. Niemerg, D. Robinson, and L. Livnev, “YieldSpace: An Automated Liquidity Provider for Fixed Yield Tokens,” 2020. [Online]. Available: https://yield.is/YieldSpace.pdf
  * [90] C. Slamka, B. Skiera, and M. Spann, “Prediction Market Performance and Market Liquidity: A Comparison of Automated Market Makers,” _IEEE Transactions on Engineering Management_ , vol. 60, no. 1, pp. 169–185, Feb. 2013, conference Name: IEEE Transactions on Engineering Management.
  * [91] A. Carvalho, D. Silveira, R. A. Ely, and D. O. Cajueiro, “A Logarithmic Market Scoring Rule Agent-based Model to Evaluate Prediction Markets,” Rochester, NY, May 2022. [Online]. Available: https://papers.ssrn.com/abstract=4103827
  * [92] BlockScience. (2022) Alpha bonds: Risk-adjusted bonding curves for financing impact. BlockScience. [Online]. Available: https://medium.com/block-science/alpha-bonds-risk-adjusted-bonding-curves-for-financing-impact-5be949fbc5a0
  * [93] W. Lau. (2018) On single bonding curves for continuous token models. medium.com. [Online]. Available: https://medium.com/thoughtchains/on-single-bonding-curves-for-continuous-token-models-a167f5ffef89
  * [94] S. Agrawal, E. Delage, M. Peters, Z. Wang, and Y. Ye, “A unified framework for dynamic pari-mutuel information market design,” in _Proceedings of the 10th ACM conference on Electronic commerce_. Stanford California USA: ACM, Jul. 2009, pp. 255–264. [Online]. Available: https://dl.acm.org/doi/10.1145/1566374.1566412
  * [95] F. Martinelli and N. Mushegian, “Balancer: A non-custodial portfolio manager, liquidity provider, and price sensor.” 2019. [Online]. Available: https://balancer.fi/whitepaper.pdf
  * [96] Balancer, “Managed Pools | Balancer,” 2023. [Online]. Available: https://docs.balancer.fi/concepts/pools/managed.html
  * [97] mStable, “Pools | mStable Docs,” 2023. [Online]. Available: https://docs.mstable.org/
  * [98] Ref.Finance, “Ref.Finanace Docs,” 2023. [Online]. Available: https://guide.ref.finance/
  * [99] THORChain, “Liquidity | THORChain,” 2023. [Online]. Available: https://docs.thorchain.org/thorchain-finance/continuous-liquidity-pools
  * [100] Unsiwap, “The Uniswap Protocol | Uniswap,” 2023. [Online]. Available: https://docs.uniswap.org/concepts/uniswap-protocol
  * [101] Sushiswap, “Sushi: Be a Crypto Chef with Sushi,” 2023. [Online]. Available: https://docs.sushi.com/pdf/whitepaper.pdf
  * [102] G. Angeris, H.-T. Kao, R. Chiang, C. Noyes, and T. Chitra, “An analysis of Uniswap markets,” Feb. 2021, arXiv:1911.03380 [cs, math, q-fin]. [Online]. Available: http://arxiv.org/abs/1911.03380
  * [103] S. Balasanov. (2020) Bonding curves in depth: Intuition & parametrization. relevant.community. [Online]. Available: https://blog.relevant.community/bonding-curves-in-depth-intuition-parametrization-d3905a681e0a
  * [104] S. d. l. Rouviere. (2017) Tokens 2.0: Curved token bonding in curation markets. medium.com. [Online]. Available: https://medium.com/@simondlr/tokens-2-0-curved-token-bonding-in-curation-markets-1764a2e0bee5

## Supplementary Material

##  VIII Overview of the Dimensions and Characteristics in the AMM Taxonomy

TABLE I: Overview of the AMM taxonomy Group | Dimension |  Description | Characteristic
---|---|---|---
Governance | Governance Model |  The decision model for parameter adjustments of an AMM. | Centralized
Decentralized
Parameter Adjustment |  The functionality to change parameters of the AMM over time. | Automatic
Fixed
| Manual
Trading Fee Adjustment |  The adjustment of trading fees charged by an AMM. | Dynamic
Static
Liquidity | Liquidity Changeability |  Liquidity changeability indicates whether the amount of available liquidity in the AMM can vary. | Prescribed
Variable
Liquidity Provider Permission |  The specification of what market participants are allowed to deposit tokens into liquidity pools. | Open
Permissioned
Number of Tokens per Liquidity Pool |  The variety of tokens that can be deposited in one liquidity pool. | Two
Three or More
Risk Management |  The mechanisms to manage the risk of holding eventually volatile tokens. | Imbalance Surcharges
Loss Insurance
| No Risk Management
Source of Liquidity |  The source of liquidity for an AMM can be external from liquidity providers or internal by token supply sovereignty. | External
Internal
Supported Trading Pairs |  The token pairs that can be traded against each other using an AMM. | Open
Restricted
Trading | Interoperability |  The capability of an AMM to execute transactions across multiple infrastructures of cryptoeconomic systems. | Interoperable
Non-interoperable
Limit Order Functionality |  The functionality to create limit orders. | Included
Not Included
Price Guarantee |  The process that determines token prices in cryptoeconomic systems. | No Guarantee
Price Range
Volume Dependency |  The dependency of token prices on the transaction volume in a cryptoeconomic system market. | Volume-dependent
Volume-independent
Pricing |  Information Expressiveness Pool |  The degree to which market information is incorporated into prices. | Expressive
Inexpressive
Liquidity Concentration |  The distribution of liquidity at different price levels. | Automatic
Function-based
| LP-based
Liquidity Sensitivity |  The influence strength of liquidity in the AMM on the magnitude of token price changes. | Insensitive
Sensitive
Path Deficiency |  The feasible transactions in relation to the token reserve of an AMM. | Deficient
Strictly Deficient
Path Independence |  The independence of AMM state transitions from the order of transactions with identical cumulative volume. | Path Dependent
Path Independent
Price Bounding |  The functionality to limit token prices of the AMM. | Bounded from Above
Bounded from Below
| Bounded from Above and Below
Price Discovery |  The definition of the process of discovering fair token prices based on at least one mathematical function. | Constant-sum
Constant-power-sum
| Constant-product
| Constant-product-sum
| Exponential Function
| Geometric Mean
| Logarithmic Market Scoring
| Price Adoption
Token Price Source |  The source of fair token prices that are used by the AMM to quote bid/ask token prices. | External
Internal
Translation invariance |  The payoff from a portfolio consisting of equal amounts of each asset. | Non-translation Invariant
Translation Invariant


††thanks: (corresponding author)

# Matrix-Completion Quantum State Tomography

Ahmad Farooq  Junaid ur Rehman  Hyundong Shin  Department of Electronics and
Information Convergence Engineering, Kyung Hee University,
1732 Deogyeong-daero, Yongin-si, Gyeonggi-do 17104, Korea<EMAIL_ADDRESS>http://cctlab.khu.ac.kr

###### Abstract

The deployment of intermediate- and large-scale quantum devices necessitates
the development of efficient full state tomographical techniques for quantum
benchmarks. Here, we introduce a matrix filling-based method for tomography of
pure quantum states, called the matrix-completion quantum state tomography.
This method requires only $2n+1$ local Pauli operators and minimal post-
processing for $n$-qubit states. Numerical results show that our method is
highly efficient on superconducting real quantum devices and achieves better
fidelity estimates of multiqubit quantum states as compared to contemporary
pure state tomography methods. These desirable features of the matrix-
completion quantum state tomography protocol make it suitable for the
benchmarking of intermediate- and large-scale quantum devices dealing mainly
with pure quantum states.

##  1 Introduction

Noisy intermediate-scale quantum (NISQ) devices consisting of hundreds of
qubits will be available soon [1]. Several technologies for these NISQ devices
are being pursued such as superconducting quantum circuits [2], trapped ions
[3], quantum dot [4], cold atoms [5], and photonic platforms [6]. These NISQ
computers are expected to perform tasks that surpass the capability of the
most powerful classical computers available today [7]. However, noisy quantum
gates and decoherence limits prevent exhibiting a clean enough improvement
over the existing current classical computing devices for complex algorithms.
With the advent of the NISQ era, we come across a paradox: How will we
validate a quantum device confirming that it is producing the desired result
that it is designed for? For characterization, certification, and benchmarking
[8] of these noisy devices, quantum state tomography comes into play, which is
the gold standard for the reconstruction of a quantum state [9].
Reconstruction of the quantum state from measurements on the replica of an
unknown given quantum state is termed as the quantum state tomography. Quantum
state tomography generally consists of a two-step process: the first is
collecting the data from optimized measurement design on quantum systems; the
second is the classical post-processing of the gathered data. Quantum state
tomography problem becomes intractable due to an exponential growth of the
system size with increase in the number of qubits under consideration [10,
11].

A conventional state standard tomography employs $d^{2}$ or more measurement
settings, where $d=2^{n}$ for $n$ qubits [12, 13, 14, 15]. A simple counting
argument suggests that only $O\left(d\right)$ measurement settings are
sufficient to perform the tomography of pure quantum states [16, 17].
Compressed sensing and low-rank matrix recovery from sparse matrix algorithms
have been developed to achieve this bound [18, 19, 20]. In [21, 22], the
authors proposed $d+1$ mutually unbiased bases measurements for _full_ quantum
state reconstruction. The states with special properties, for instance, matrix
product states [23] or permutationally invariant quantum states [24] also lead
to a significant reduction in the number of quantum measurement settings. The
pure quantum state can also be retrieved with only five and three measurement
settings given in [25, 26, 27]. Recently noise resilient and robust self-
guided quantum state tomography is proposed [28, 29, 30]. Five basis
measurement has the highest performance among all the non-adaptive quantum
state tomography algorithm.

All the aforementioned tomography algorithms employ entangled bases in the
measurement setting. For the implementation of entangled bases on NISQ
devices, we apply sets of unitary transformations followed by the
computational basis measurement. The controlled-NOT (CNOT) gate is an
essential transformation requierd for implementing these sets of entangled
measurements. The implementation of CNOT gate on quantum devices introduces a
larger error due to experimental difficulties. Moreover, the circuit depth is
quite high for the large number of qubit systems, which results in the
decoherence of qubits. Hence, these entangled bases significantly reduce the
performance of state estimation task. The introduction of local basis
measurement for state reconstruction can be a massive catalyst for the
benchmarking of quantum devices. For this purpose, local basis measurements
are introduced in [31]. They have demonstrated the task of tomography of pure
quantum state by using $kn+1$ measurement bases, where $k\geq 2$. Their
algorithm is based on solving several systems of linear equations. The
required number of bases increases ($k>2$) if the determinant of the linear
system of equations vanishes. The performance is quite low as compared to the
numerical results of entangled measurement algorithms.

In this paper, we present a matrix filling-based quantum state estimation
algorithm for pure states, called the matrix-completion quantum state
tomography. Our algorithm utilizes only $2n+1$ local Pauli measurement bases
for an $n$-qubit state. We first experimentally obtain a sufficient number of
elements of the density matrix such that a matrix-completion algorithm for
rank-1 matrices can be employed. We then fill the missing entries by taking
any $2\times 2$ submatrix in the density matrix using the rank one constraint.
Simulation and experimental numerical examples demonstrate that the
performance of our algorithm is notably high as compared to the existing
algorithms. The matrix-completion quantum state tomography also has both
computational complexity and memory storage low which is the order of
$O\left(d^{2}\right)$.

##  2 Method

In this section, we outline our protocol for tomography of pure quantum states
by matrix filling. Our technique requires $2n+1$ local measurement settings
for an $n$-qubit system. The main ingredient of this technique is the
algorithm for completing rank-1 matrices [32, Section IV.8]. This algorithm
makes use of the fact that all columns/rows of a rank-1 matrix are multiples
of each other. Alternatively, determinants of all $2\times 2$ submatrices must
be zero. We first experimentally obtain a sufficient number of entries of the
density matrix of a pure state. Then, we employ the matrix completion to
obtain the complete density matrix of our state of interest.

Filling the missing entries of a rank-1 matrix is directly connected to the
problem of finding cycles in a graph [32]. The rank-1 matrix of dimension
$d\times d$ can be fully reconstructed by knowing only $2d-1$ entries of the
given matrix. These $2d-1$ elements form a spanning tree in the row-column
graph. The successful reconstruction of missing entries of the given matrix
depends on the tree reaching all nodes with no loop. The tree with a loop in
the row-column graph does not guarantee rank-1 matrix construction. If we know
the $2d-1$ entries of the matrix which do not form the cycle in the row-column
tree graph, then we can construct successfully all the other entries of the
matrix by utilizing the fact that every $2\times 2$ determinant must be zero
in the rank-1 matrix. The row-column graph is shown in Figure 1.

(a) Success

(b) Success

(c) Failure

Figure 1:  Criteria to successfully construct the rank-1 $d\times d$ matrix
from the $2d-1$ entries. Edge connection between $i$th row node and $j$th
column node represent the matrix element entry $a_{ij}$. By knowing only
$2d-1$ entries of the matrix, we can construct the whole rank one matrix of
dimension $d\times d$ when the edges connection between row-column tree do not
make any cycle. The tree diagram is shown for $4\times 4$. In $\mathbb{(a)}$
and $\mathbb{(b)}$, none of the edges make the complete cycle while
$\mathbb{(c)}$ shows that the edges connection form a complete loop.  Figure
2: Overview of the matrix-completion quantum state tomography. The green color
represents the entries that are obtained experimentally. The light green color
shows only the real part of entries of the matrix. The red color represents
the entries that are obtained by matrix completion. The dark blue color
represents entries that can be obtained experimentally or from the algorithm.
We first obtain the diagonal entries of the rank-one matrix using
computational-basis measurement. Using $U=H$ in the above circuit enables us
to obtain the real component of the entries while using $U=S^{\dagger}H$
provides the Imaginary components of entries. Determinants of $2$ by $2$
submatrices of the light red color is used to find the missing entries in that
submatrix.

In our algorithm, we perform local Pauli measurements on each subsystem of
multipartite pure quantum state. We first employ the computational basis
measurement to obtain the diagonal elements of the unknown density matrix.
Next, we measure $n$-qubit systems in Pauli measurement setting

$\displaystyle\Lambda_{j}^{i}=I_{2}^{\otimes i-1}\otimes\sigma_{j}^{i}\otimes
I_{2}^{\otimes n-i},$ (1)

where $i=1,2,\cdots,n$, with
$\sigma_{j}^{i}\in\left\\{\sigma_{1},\sigma_{2}\right\\}$ are Pauli $X$
($\sigma_{1}$) and Pauli $Y$ ($\sigma_{2}$) matrices.

We begin by assuming that we have access to $N$ copies of a $n$-qubit
multipartite unknown pure state $\rho=\ket{\psi}\bra{\psi}$. In the first step
of our algorithm we obtain the diagonal elements of $\rho$ by measuring
$N/(2n+1)$ of its copies in the computational basis of the $d$-dimensional
Hilbert space. From the measurement results, diagonal elements of $\rho$ can
be directly obtained as

$\displaystyle\hat{\rho}_{i,i}=\frac{\left(2n+1\right)N_{i}}{N},\text{ for
}i\in\mathbb{Q}_{d},$ (2)

where $\mathbb{Q}_{d}=\left\\{0,1,\cdots,d-1\right\\}$, $N_{i}$ is the number
of times measurement result corresponding to $\ket{i}$ was obtained in the
first step and $\hat{a}$ denotes an estimate of $a$.

The off-diagonal element $\rho_{j,k}$ of $\rho$ can be obtained by measuring
it in the eigenbasis of Pauli operators pair $\Lambda_{1}^{i}$ and
$\Lambda_{2}^{i}$. This can be seen by first noticing that the eigenvectors of
$\Lambda_{1}^{i}$ and $\Lambda_{2}^{i}$ are

$\displaystyle\ket{V_{1,\pm 1}^{2^{i}\nu+\zeta,2^{i}\nu+\zeta+2^{i-1}}}$
$\displaystyle=\frac{1}{\sqrt{2}}\left(\ket{2^{i}\nu+\zeta}\pm\ket{2^{i}\nu+\zeta+2^{i-1}}\right)$
(3) $\displaystyle\ket{V_{2,\pm 1}^{2^{i}\nu+\zeta,2^{i}\nu+\zeta+2^{i-1}}}$
$\displaystyle=\frac{1}{\sqrt{2}}\left(\ket{2^{i}\nu+\zeta}\pm\dot{\iota}\ket{2^{i}\nu+\zeta+2^{i-1}}\right),$
(4)

where $\nu\in\mathbb{Q}_{\frac{d}{2}}$ and $\zeta\in\mathbb{Q}_{2^{i-1}}$.

Input: $N$ copies of the $n$-qubit pure state $\ket{\psi}$.

Output: Estimate $\ket{\hat{\psi}}$ of $\ket{\psi}$

1 $\hat{\rho}_{i,i}\leftarrow\left|\braket{\psi}{i}\right|^{2}$,
$\blacktriangleright$ Computational basis measurement

2 for  _$i\in 1\rightarrow n$_ do

3 for  _$x\in 1\rightarrow 2$ _ do

4 $\Lambda_{x}^{i}\leftarrow I_{2}^{\otimes i-1}\otimes\sigma_{x}^{i}\otimes
I_{2}^{\otimes n-i}$ , $\blacktriangleright$ Pauli operators

5 $\ket{V_{x,\pm
1}^{2^{i}\nu+\zeta,2^{i}\nu+\zeta+2^{i-1}}}\leftarrow\mathrm{eig}\left(\Lambda_{x}^{i}\right)$,
$\blacktriangleright$ where $\nu\in\mathbb{Q}_{\frac{d}{2}}$ and
$\zeta\in\mathbb{Q}_{2^{i-1}}$

6 $\Pi_{x,\pm 1}^{j,k}\leftarrow\ket{V_{x,\pm 1}^{j,k}}\bra{V_{x,\pm
1}^{j,k}}$, $\blacktriangleright$ where $j=2^{i}\nu+\zeta$ and
$k=2^{i}\nu+\zeta+2^{i-1}$

7 $\hat{p}_{x,\pm 1}^{j,k}\leftarrow\braket{\psi}{\Pi_{x,\pm 1}^{j,k}}{\psi}$,
$\blacktriangleright$ Local Pauli measurements

8

9$\hat{\rho}_{j,k}\leftarrow\frac{1}{2}\left(-\hat{p}_{1,-1}^{j,k}+\hat{p}_{1,1}^{j,k}-\iota\hat{p}_{2,-1}^{j,k}+\iota\hat{p}_{2,1}^{j,k}\right)$
, $\blacktriangleright$ Density matrix elements entries

10 $\hat{\rho}_{k,j}\leftarrow\hat{\rho}_{j,k}^{\dagger}$,
$\blacktriangleright$ Hermitian symmetric

11
$\hat{\rho}_{ij}\leftarrow\frac{\hat{\rho}_{ri}\hat{\rho}_{jr}}{\hat{\rho}_{rr}}$,
$\blacktriangleright$ Matrix completion of any $2\times 2$ submatrix

12
$\hat{\rho}\leftarrow\frac{\hat{\rho}}{\operatorname{\mathrm{tr}}\left(\hat{\rho}\right)}$,
$\blacktriangleright$ Normalization

13 $\ket{\hat{\psi}}\leftarrow\mathrm{eig}\left(\hat{\rho}\right)$ ,
$\blacktriangleright$ Eigenvector with highest eigenvalue.

return $\ket{\hat{\psi}}$

Algorithm 1 Pure State Quantum Tomography by Matrix Completion

These orthonormal bases build a complete projector system with elements

$\displaystyle\Pi_{x,-1}^{j,k}$
$\displaystyle=\ket{V_{x,-1}^{j,k}}\bra{V_{x,-1}^{j,k}}$ (5)
$\displaystyle\Pi_{x,1}^{j,k}$
$\displaystyle=\ket{V_{x,1}^{j,k}}\bra{V_{x,1}^{j,k}}.$ (6)

where $x\in\left\\{1,2\right\\}$, $j=2^{i}\nu+\zeta$ and
$k=2^{i}\nu+\zeta+2^{i-1}$. Let $p_{x,m}^{j,k}$ be the probability of
obtaining the measurement outcome corresponding to the projector
$\Pi_{x,m}^{j,k}$. Then, we have

$\displaystyle p_{1,-1}^{j,k}$
$\displaystyle=\frac{1}{2}\left(\rho_{j,j}-\rho_{j,k}-\rho_{k,j}+\rho_{k,k}\right)$
(7) $\displaystyle p_{1,1}^{j,k}$
$\displaystyle=\frac{1}{2}\left(\rho_{j,j}+\rho_{j,k}+\rho_{k,j}+\rho_{k,k}\right)$
(8) $\displaystyle p_{2,-1}^{j,k}$
$\displaystyle=\frac{1}{2}\left(\rho_{j,j}+\dot{\iota}\rho_{j,k}-\dot{\iota}\rho_{k,j}+\rho_{k,k}\right)$
(9) $\displaystyle p_{2,1}^{j,k}$
$\displaystyle=\frac{1}{2}\left(\rho_{j,j}-\dot{\iota}\rho_{j,k}+\dot{\iota}\rho_{k,j}+\rho_{k,k}\right),$
(10)

where $\rho_{j,k}=\braket{j}{\rho}{k}$ is the element of $\rho$ at $(j,k)$th
index. From the hermiticity of $\rho$, we have
$\rho_{k,j}=\rho_{j,k}^{\dagger}$. Using this fact, we get
$\rho_{j,k}+\rho_{k,j}=2\mathrm{Re}\left\\{\rho_{j,k}\right\\}$ and
$\rho_{j,k}-\rho_{k,j}=2\mathrm{Im}\left\\{\rho_{j,k}\right\\}$. Consequently,
we can obtain $\rho_{j,k}$ as

$\displaystyle\rho_{j,k}=\frac{1}{2}\left(-p_{1,-1}^{jk}+p_{1,1}^{jk}-\iota
p_{2,-1}^{jk}+\iota p_{2,1}^{jk}\right).$ (11)

From $\rho_{jk}$, we can easily get $\rho_{k,j}=\rho_{j,k}^{\dagger}$.

The complete protocol for constructing the density matrix of a pure quantum
state $\rho$ is as follows:

  1. 1.

Measure $\rho$ in the computational basis to obtain the diagonal entries of
the density matrix through (2).

  2. 2.

Obtain entries of the density matrix $\hat{\rho}_{j,k}$. These entries are
obtained by measuring in all Pauli operators measurement setting of (1) and
using (11) as described above.

Figure 3:  Median Infidelities of $10^{3}$ randomly generated pure state from
matrix-completion quantum state tomography (MC-QST) and modified five basis
algorithm as a function of a number of total measurements. The performance of
MC-QST improves as compared to the five basis algorithm as the number of
qubits increases.

  3. 3.

Since $\rho$ is pure, the corresponding density matrix has rank one. Thus, its
remaining entries can be obtained by [32, Section IV.8]

$\displaystyle\hat{\rho}_{ij}=\frac{\hat{\rho}_{ri}\hat{\rho}_{jr}}{\hat{\rho}_{rr}}.$
(12)

This is because, in any rank-one matrix, every $2\times 2$ determinant must be
zero. The computational complexity of this step is $O\left(d^{2}\right)$ which
is the total computational complexity of our algorithm.

A schematic diagram of matrix-completion quantum state tomography algorithm is
shown in Figure 2 and complete procedure is outlined in Algorithm 1.

##  3 Results

We can certify the purity of our unknown quantum state using our algorithm
without the need of any extra measurement. A density matrix $\rho$ is said to
be pure if and only if the equation

$\displaystyle|\rho_{i,j}|^{2}=|\rho_{i,i}||\rho_{j,j}|,$ (13)

holds for every $i,j=1,2,\cdots,d$. We can easily verify the purity of unknown
quantum state from measured structure obtained in Figure 2 by employing (13)
on any number of elements of the constructed density matrix.

To gauge the accuracy of state tomography, we use the common figure of merit,
infidelity, which characterizes the distance between these states. Infidelity
is defined as

$\displaystyle
1-F\left(\rho,\sigma\right)=1-\left(\operatorname{\mathrm{tr}}\sqrt{\sqrt{\sigma}\rho\sqrt{\sigma}}\right)^{2}$
(14)

where $F\left(\rho,\sigma\right)$ is the fidelity between $\rho$ and $\sigma$.

Figure 4: Median infidelity as a function of number of qubits by varying the
measurement copies in each measurement setting. The median infidelities of
$10^{3}$ Haar-random pure quantum states obtained from matrix-completion
quantum state tomography (MC-QST) and algorithm of [31] are plotted against
the number of qubits by utilizing $N_{\mathrm{tot}}=10^{4}$ to $10^{9}$ copies
(starting from above) total. We can see that the median infidelities of our
algorithm are better than the previously established technique for the same
number of qubits and total measurements.

We first compare our algorithm with the performance of improved estimation of
five basis algorithm given in [33]. First, measurement in the computational
basis gives the amplitude structure $\left|c_{i}\right|$ of the given unknown
quantum state $\ket{\psi}=\sum_{i=0}^{d-1}c_{i}\ket{i}$. Then, we employ the
permutation unitary on the given unknown quantum state such that

$\displaystyle\ket{\psi_{p}}=U_{p}\ket{\psi}=\sum_{i=0}^{d-1}c_{\left[i\right]}\ket{i},$
(15)

where the amplitudes have descending order as
$\left|c_{\left[0\right]}\right|\geq\left|c_{\left[1\right]}\right|\geq\cdots\geq\left|c_{\left[d-1\right]}\right|$
and the permutation unitary

$\displaystyle U_{p}=\sum_{i=0}^{d-1}\ket{i}\bra{\left[i\right]}.$ (16)

We use (11) used in matrix-completion quantum state tomography to find other
entries. To further improve the accuracy, we first find all entries of first
column and row in the density matrix using our algorithm and construct the
complete density matrix $\rho$ in a single step as follows

$\displaystyle\hat{\rho}_{i,j}=\frac{\hat{\rho}_{1,i}\hat{\rho}_{j,1}}{\hat{\rho}_{1,1}}.$
(17)

Second, we obtain the complex phase $e^{\dot{\iota}\hat{\phi}_{i}}$ of
estimated state from our algorithm and construct the pure quantum state using
these phases and amplitudes in (2) by

$\displaystyle\ket{\hat{\psi}_{p}}=\sum_{i=0}^{d-1}|c_{i}^{{}^{\prime}}|e^{\dot{\iota}\hat{\phi}_{i}}\ket{i}.$
(18)

By applying the inverse of unitary, we revert back to the desired quantum
state

$\displaystyle\ket{\hat{\psi}}=U_{p}^{\dagger}\ket{\hat{\psi}_{p}}.$ (19)

We plot median infidelity of $10^{3}$ pure randomly generated states according
to Haar measure by employing matrix-completion quantum state tomography
algorithm with improved five basis method. Five basis uses two entangled basis
to estimate the pure quantum state which has high gate errors and decoherence
in practical settings. Using our algorithm, not only we overcome this
deficiency for practical quantum computers but also surpass the accuracy in
numerical simulations as demonstrated in Figure 3.

To determine the performance of our procedure, we show the median infidelity
of $10^{3}$ Haar-random pure quantum states on $N_{\mathrm{tot}}=10^{4}$ to
$10^{9}$ copies as a function of the number of qubits in Figure 4. For
comparison, we also plot the median infidelity of scalable estimation that
also uses the local bases as proposed in [31]. Figure 4 shows that our
algorithm has significant improvement over the existing algorithm of local
bases measurement-based state tomography. The performance increase becomes
more prominent when the number of qubits is increased.

Figure 5:  Median infidelities of two-qubit Haar-random states as a function
of total measurements. The median values are calculated over $10^{2}$ states
on real device and $10^{3}$ states on fake devices. Graph shows a comparison
of matrix-completion quantum state tomography (MC-QST) with the algorithm of
[31]. We can clearly see that median fidelity of our algorithm outperforms the
method [31].

We have also implemented our technique on a superconducting quantum computer
to experimentally verify our results [34]. We use 7-qubit ibmq-casablanca
device for these experiments. The device has average measurement and CNOT
errors of $2.653e^{-2}$ and $8.374e^{-3}$ respectively. We also use the Fake-
Casablanca which uses the same noise model as a real device to obtain more
robust estimates by increasing the number of experiments. Figure 2 shows the
circuit that we implement on the IBM quantum device where

$\displaystyle H=\begin{bmatrix}1&1\\\ 1&-1\end{bmatrix},\hskip
7.11317pt\text{and}\hskip 7.11317ptS^{\dagger}=\begin{bmatrix}1&0\\\
0&e^{-\frac{\dot{\iota}\pi}{2}}\end{bmatrix}.$ (20)

We produced $10^{2}$ Haar-random pure two-qubit states on the real device. For
fake device, we utilized $10^{3}$ pure two-qubit states. We plot the median
fidelity of our algorithm and scalable estimation of [31] in Figure 5.
Numerical results indicate that we can precisely benchmark the cloud-based IBM
quantum devices.

Our algorithm is more effective when the density matrix is less sparse. To
deal with the sparse matrix problem, we first measure in computational basis
and see the structure of vanishing coefficients. Depending on the structure,
we prepare the local unitary and apply it to the quantum state before
measuring on a local basis. Greenberger-Horne-Zeilinger (GHZ) state is one of
the examples of this type of states. We prepare and measure three-qubits GHZ
state in the computational basis on an IBM device. We find out that it has
only two dominant diagonal entries and the remaining entries are very small or
zero. To overcome this issue, we prepare the local unitary of the form

$\displaystyle V=H\otimes H\otimes H,$ (21)

and apply on the state

$\displaystyle\ket{\psi^{\prime}}=V\ket{\psi}.$ (22)

After estimating all the coefficients of the quantum state, we apply the
inverse of the unitary matrix to get back the original prepared quantum state

$\displaystyle\ket{\psi}=V^{\dagger}\ket{\psi^{\prime}}.$ (23)

In Figure. 6, we demonstrate the real and imaginary parts of the
experimentally reconstructed GHZ state through our algorithm. We generate
eleven GHZ states and select the median fidelity density matrix. For three
qubits GHZ states, we can reconstruct the density matrix with $97\%$ median
fidelity.

(a) Re$\left(\rho\right)$

(b) Im$\left(\rho\right)$

Figure 6:  Reconstructing three-qubit GHZ state on a superconducting
processor. Real and imaginary parts of the matrix coefficients of the
experimentally estimated GHZ state on ibmq-casablanca device are shown.

##  4 Conclusion

Entangling gates act as a bottleneck in the performance of accurate estimation
and benchmarking tasks in NISQ devices. In this paper, we proposed an
efficient algorithm for the estimation of pure states that is computationally
efficient and requires only local measurements. Implementing the local Pauli
bases on any quantum devices requires only local gates such as $H$ and $S$,
which can be implemented with relatively more precision as compared to
entangling gates. Furthermore, our algorithm reduces the circuit depth in real
quantum devices, which is usually high when implementing entangling gates.
This reduction of circuit depth can play a vital role where gate errors and
decoherence rates are high. We observe the $97\%$ fidelity of qutrit GHZ state
which is, to the best of our knowledge, the highest ever reported on
superconducting quantum devices. Experimental results demonstrate that our
technique is extremely efficient for benchmarking of cloud-based NISQ
computers available today.

## Acknowledgments

We acknowledge the use of the IBM Q for this work. The views expressed are
those of the authors and do not reflect the official policy or position of IBM
or the IMB Q team. This work was supported by the National Research Foundation
of Korea (NRF) grant funded by the Korea government (MSIT) (No.
2019R1A2C2007037) and by the MSIT (Ministry of Science and ICT), Korea, under
the ITRC (Information Technology Research Center) support program
(IITP-2021-0-02046) supervised by the IITP (Institute for Information $\&$
Communications Technology Planning $\&$ Evaluation).

## References

  * Preskill [2018] John Preskill.  Quantum Computing in the NISQ era and beyond.  _Quantum_ , 2:79, August 2018.  ISSN 2521-327X.  doi: 10.22331/q-2018-08-06-79.
  * Kandala et al. [2017] Abhinav Kandala, Antonio Mezzacapo, Kristan Temme, Maika Takita, Markus Brink, Jerry M Chow, and Jay M Gambetta.  Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets.  _Nature_ , 549(7671):242–246, September 2017\.  doi: 10.1038/nature23879.
  * Zhang et al. [2017] Jiehang Zhang, Guido Pagano, Paul W Hess, Antonis Kyprianidis, Patrick Becker, Harvey Kaplan, Alexey V Gorshkov, Z-X Gong, and Christopher Monroe.  Observation of a many-body dynamical phase transition with a 53-qubit quantum simulator.  _Nature_ , 551(7682):601–604, November 2017.  doi: 10.1038/nature24654.
  * Loss and DiVincenzo [1998] Daniel Loss and David P. DiVincenzo.  Quantum computation with quantum dots.  _Phys. Rev. A_ , 57:120–126, January 1998.  doi: 10.1103/PhysRevA.57.120.
  * Bernien et al. [2017] Hannes Bernien, Sylvain Schwartz, Alexander Keesling, Harry Levine, Ahmed Omran, Hannes Pichler, Soonwon Choi, Alexander S Zibrov, Manuel Endres, Markus Greine, et al.  Probing many-body dynamics on a 51-atom quantum simulator.  _Nature_ , 551(7682):579–584, November 2017.  doi: 10.1038/nature24622.
  * Reck et al. [1994] Michael Reck, Anton Zeilinger, Herbert J. Bernstein, and Philip Bertani.  Experimental realization of any discrete unitary operator.  _Phys. Rev. Lett._ , 73:58–61, July 1994.  doi: 10.1103/PhysRevLett.73.58.
  * Terhal [2018] Barbara M Terhal.  Quantum Supremacy, here we come.  _Nat. Phys._ , 14(6):530–531, April 2018.  doi: 10.1038/s41567-018-0131-y.
  * Eisert et al. [2020] Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud, and Elham Kashefi.  Quantum certification and benchmarking.  _Nat. Rev. Phys._ , 2(7):382–390, July 2020.  doi: 10.1038/s42254-020-0186-4.
  * Torlai and Melko [2020] Giacomo Torlai and Roger G. Melko.  Machine-learning quantum states in the nisq era.  _Annu. Rev. Condens. Matter Phys._ , 11(1):325–344, March 2020.  doi: 10.1146/annurev-conmatphys-031119-050651.
  * Shabani et al. [2011] A. Shabani, R. L. Kosut, M. Mohseni, H. Rabitz, M. A. Broome, M. P. Almeida, A. Fedrizzi, and A. G. White.  Efficient measurement of quantum dynamics via compressive sensing.  _Phys. Rev. Lett._ , 106:100401, March 2011.  doi: 10.1103/PhysRevLett.106.100401.
  * Lloyd et al. [2014] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost.  Quantum principal component analysis.  _Nat. Phys._ , 10(9):631–633, July 2014.  doi: 10.1038/nphys3029.
  * Banaszek et al. [1999] K. Banaszek, G. M. D’Ariano, M. G. A. Paris, and M. F. Sacchi.  Maximum-likelihood estimation of the density matrix.  _Phys. Rev. A_ , 61:010304, December 1999.  doi: 10.1103/PhysRevA.61.010304.
  * Opatrný et al. [1997] T. Opatrný, D.-G. Welsch, and W. Vogel.  Least-squares inversion for density-matrix reconstruction.  _Phys. Rev. A_ , 56:1788–1799, September 1997.  doi: 10.1103/PhysRevA.56.1788.
  * Qi et al. [2013] Bo Qi, Zhibo Hou, Li Li, Daoy Dongi, Guoyong Xiang, and Guangcan Guo.  Quantum state tomography via linear regression estimation.  _Sci. Rep._ , 3:3496, December 2013.  doi: 10.1038/srep03496.
  * Blume-Kohout [2010] Robin Blume-Kohout.  Optimal, reliable estimation of quantum states.  _New J. Phys._ , 12(4):043034, April 2010.  doi: 10.1088/1367-2630/12/4/043034.
  * Dodonov and Man’ko [1997] V.V. Dodonov and V.I. Man’ko.  Positive distribution description for spin states.  _Phys. Lett. A_ , 229(6):335–339, February 1997\.  ISSN 0375-9601.  doi: https://doi.org/10.1016/S0375-9601(97)00199-0.
  * Amiet and Weigert [1999] Jean-Pierre Amiet and Stefan Weigert.  Reconstructing a pure state of a spinsthrough three stern-gerlach measurements.  _J. Phys. A: Math. Gen._ , 32(15):2777–2784, January 1999.  doi: 10.1088/0305-4470/32/15/006.
  * Steffens et al. [2017] A Steffens, C A Riofrío, W McCutcheon, I Roth, B A Bell, A McMillan, M S Tame, J G Rarity, and J Eisert.  Experimentally exploring compressed sensing quantum tomography.  _Quantum Sci. Technol._ , 2(2):025005, May 2017\.  doi: 10.1088/2058-9565/aa6ae2.
  * Kueng et al. [2017] Richard Kueng, Holger Rauhut, and Ulrich Terstiege.  Low rank matrix recovery from rank one measurements.  _Appl. and Comp. Har. Anal._ , 42(1):88–116, January 2017.  ISSN 1063-5203.  doi: https://doi.org/10.1016/j.acha.2015.07.007.
  * Bolduc et al. [2017] Eliot Bolduc, George C Knee, Erik M Gauger, and Jonathan Leach.  Projected gradient descent algorithms for quantum state tomography.  _npj Quantum Inf._ , 3(1):1–9, October 2017.
  * Wootters and Fields [1989] William K Wootters and Brian D Fields.  Optimal state-determination by mutually unbiased measurements.  _Ann. Phys._ , 191(2):363 – 381, October 1989\.  ISSN 0003-4916.  doi: https://doi.org/10.1016/0003-4916(89)90322-9.
  * Adamson and Steinberg [2010] R. B. A. Adamson and A. M. Steinberg.  Improving quantum state estimation with mutually unbiased bases.  _Phys. Rev. Lett._ , 105:030406, July 2010.  doi: 10.1103/PhysRevLett.105.030406.
  * Cramer et al. [2010] Marcus Cramer, Martin B Plenio, Steven T Flammia, Rolando Somma, David Gross, Stephen D Bartlett, Olivier Landon-Cardinal, David Poulin, and Yi-Kai Liu.  Efficient quantum state tomography.  _Nat. Commun._ , 1(1):1–7, December 2010.  doi: 10.1038/ncomms1147.
  * Tóth et al. [2010] G. Tóth, W. Wieczorek, D.Gross, R. Krischek, C. Schwemmer, and H.Weinfurter.  Permutationally invariant quantum tomography.  _Phys. Rev. Lett._ , 105:250403, December 2010.  doi: 10.1103/PhysRevLett.105.250403.
  * Goyeneche et al. [2015] D. Goyeneche, G. Ca nas, S. Etcheverry, E. S. Gómez, G. B. Xavier, G. Lima, and A. Delgado.  Five measurement bases determine pure quantum states on any dimension.  _Phys. Rev. Lett._ , 115:090401, August 2015.  doi: 10.1103/PhysRevLett.115.090401.
  * Carmeli et al. [2016] Claudio Carmeli, Teiko Heinosaari, Michael Kech, Jussi Schultz, and Alessandro Toigo.  Stable pure state quantum tomography from five orthonormal bases.  _EPL_ , 115(3):30001, August 2016.  doi: 10.1209/0295-5075/115/30001.
  * Zambrano et al. [2020] L. Zambrano, L. Pereira, D. Martínez, G. Ca nas, G. Lima, and A. Delgado.  Estimation of pure states using three measurement bases.  _Phys. Rev. Applied_ , 14:064004, December 2020.  doi: 10.1103/PhysRevApplied.14.064004.
  * Rambach et al. [2021] Markus Rambach, Mahdi Qaryan, Michael Kewming, Christopher Ferrie, Andrew G. White, and Jacquiline Romero.  Robust and efficient high-dimensional quantum state tomography.  _Phys. Rev. Lett._ , 126:100402, March 2021.  doi: 10.1103/PhysRevLett.126.100402.
  * Ferrie [2014] Christopher Ferrie.  Self-guided quantum tomography.  _Phys. Rev. Lett._ , 113:190404, November 2014.  doi: 10.1103/PhysRevLett.113.190404.
  * Chapman et al. [2016] Robert J. Chapman, Christopher Ferrie, and Alberto Peruzzo.  Experimental demonstration of self-guided quantum tomography.  _Phys. Rev. Lett._ , 117:040402, July 2016.  doi: 10.1103/PhysRevLett.117.040402.
  * Pereira et al. [2021] L Pereira, L Zambrano, and A Delgado.  Scalable estimation of pure multi-qubit states.  _arXiv preprint arXiv:2107.05691_ , July 2021.
  * Strang [2019] Gilbert Strang.  _Linear Algebra and Learning from Data_.  Wellesley-Cambridge Press Cambridge, 2019.
  * Zambrano et al. [2019] L. Zambrano, L. Pereira, and A. Delgado.  Improved estimation accuracy of the 5-bases-based tomographic method.  _Phys. Rev. A_ , 100:022340, August 2019.  doi: 10.1103/PhysRevA.100.022340.
  * [34] 7-qubit backend: IBM Q team, IBM Q 7 Casablanca backend specification v1.2.34.  (Accessed:Sep 2021).


marginparsep has been altered.
topmargin has been altered.
marginparwidth has been altered.
marginparpush has been altered.
The page layout violates the ICML style. Please do not change the page layout,
or include packages like geometry, savetrees, or fullpage, which change it for
you. We’re not able to reliably undo arbitrary changes to the style. Please
remove the offending package(s), or layout-changing commands and try again.

Sea Ice Forecasting using Attention-based Ensemble LSTM

Anonymous Authors1

††footnotetext:  1Anonymous Institution, Anonymous City, Anonymous Region,
Anonymous Country. Correspondence to: Anonymous Author
<EMAIL_ADDRESS>
Preprint. Work in progress.

###### Abstract

Accurately forecasting Arctic sea ice from sub-seasonal to seasonal scales has
been a major scientific effort with fundamental challenges at play. In
addition to physics-based earth system models, researchers have been applying
multiple statistical and machine learning models for sea ice forecasting.
Looking at the potential of data-driven sea ice forecasting, we propose an
attention-based Long Short Term Memory (LSTM) ensemble method to predict
monthly sea ice extent up to 1 month ahead. Using daily and monthly satellite
retrieved sea ice data from NSIDC and atmospheric and oceanic variables from
ERA5 reanalysis product for 39 years, we show that our multi-temporal ensemble
method outperforms several baseline and recently proposed deep learning
models. This will substantially improve our ability in predicting future
Arctic sea ice changes, which is fundamental for forecasting transporting
routes, resource development, coastal erosion, threats to Arctic coastal
communities and wildlife.

##  1 Introduction

Over the last three decades, the warming of the sea ice in the Arctic has been
almost twice faster than the rest of the world. This phenomenon is also called
Arctic amplification (Holland & Bitz, 2003).This amplification will further
alter the climate patterns beyond the Arctic region and lead to more intense
and more frequent extreme weather events. A recent example of this is the
2021’s historic cold snap in Texas and Oklahoma, where more than 3000 daily
low temperature records were broken, resulting in at least 176 fatalities and
$195 billion economic loss Freedman et al. (2021). The sea ice plays a key
role in the Arctic climate system and it has been fallen by half since 1979
when the satellite observations were available (Serreze & Stroeve, 2015). On
current trends, the Arctic ocean could be sea ice free by 2050 (Notz &
Stroeve, 2018). Such rapid changes has profound local and global impacts on
transporting routes, resource development, coastal erosion, military and
civilian infrastructure, Arctic coastal communities (hunting and
transportation by indigenous populations), wildlife (e.g., polar bear access
to food sources).

Though most of the scientists agree that this rapid Arctic warming is a sign
of human-caused climate change, studying the causes of Arctic amplification
and forecasting sea ice has become one of the most hyped questions in the
Earth Science research (Holland et al., 2019). Current operational sea ice
forecasting systems are mainly based on coupled Earth System Models, which
estimates the solution to differential equations of fluid motion and
thermodynamics to obtain time and space dependent values for various variables
in the atmosphere, ocean or sea ice. However, these physics-based models
perform no better than simple statistical methods at lead times of two months
and beyond. Over the last few years, there are many studies focusing on sea
ice forecasting using data-driven Artificial Intelligence (AI) approaches like
machine learning and deep learning. Chi & Kim (2017) compared the Long Short-
Term Memory (LSTM) model with a traditional statistical model, and they found
that the LSTM showed good performance for 1-month sea ice concentration (SIC)
prediction, with less than 9% average monthly errors. However, there is lower
predictability during the melting season, with the root-mean-squared-error
(RMSE) of 11.09% from July to September. Wang et al. (2017) showed the
superiority of the convolutional neural networks (CNN) in SIC prediction with
an estimated RMSE of 22% compared to a multi-layer preceptron model. Kim et
al. (2019) applied deep neural networks with Bayesian model averaging ensemble
to predict the SIC in the next 10 to 20 years and found out the annual RMSE of
19.4%. More recently, Kim et al. (2020) built a novel 1-month SIC prediction
model with CNNs using eight predictors to predict SIC both temporally and
spatially. They showed that CNNs had better performance than a random forest
model and the persistence model based on the monthly trend, with the RMSE of
5.76%. Liu et al. (2021) proposed a 1-day SIC prediction model based on the
Convolutional LSTM and they concluded that the predictability of Convolutional
LSTM always performed better than that of the CNN, with an RMSE of 11.24%
through 10 consecutive days of iterative prediction.

In light of above related work, we introduce a sea ice forecasting system with
Attention-based Ensemble Long Short-Term Memory (LSTM) networks to predict
monthly sea ice extent with a lead time of 1 month. We have published our
open-access code on github 111https://github.com/big-data-lab-umbc/sea-ice-
prediction. The major goal of this study is to work on deep learning based
forecasting models that can utilize multi-temporal data to forecast daily,
weekly and monthly sea-ice extent with comparatively high accuracy. Our major
contributions are as follows.

  * •

We propose an ensembling method for multi-temporal Deep Learning models that
performs ensembling of constituent models to give optimal sea ice predictions
for next 1 month.

  * •

We introduce an attention mechanism in our ensemble that lets model pay more
or less attention to different features learned by constituent Deep Learning
models leading to lower loss and higher accuracy.

Figure 1: Overall Architecture of Attention-based LSTM Ensemble (EA-LSTM).

##  2 Data and Method

###  2.1 Dataset

In this study, we use ten atmospheric and ocean variables obtained from ERA-5
global reanalysis product and sea ice extent values, derived from sea ice
concentrations, that we obtained from the Nimbus-7 SSMR and DMSP SSM/I-SSMIS
passive microwave data version 1 Cavalieri et al. (1996) provided by the
National Snow and Ice Data Center. These variables are enlisted in Table 1. We
created two time-series combining both sea ice extent and atmospheric
variables for a span of 39 years, from 1979 to 2018. In the first time-series,
monthly gridded data during 1980-2018 has been averaged over the Arctic north
of 25∘ N using area-weighted method. In the second time-series, daily gridded
data has been averaged over the same spatial location. Throughout the
experiments, we use first 34 years of data for training and last 5 years of
data for testing.

Table 1: Variables included in the Dataset
Variable | Range | Unit
---|---|---
surface pressure | [400,1100] | hPa
wind velocity | [0,40] | m/s
specific humidity | [0,0.1] | kg/kg
air temperature | [200,350] | K
shortwave radiation | [0,1500] | $W/m^{2}$
longwave radiation | [0,700] | $W/m^{2}$
rain rate | [0,800] | mm/day
snowfall rate | [0,200] | mm/day
sea surface temperature | [200,350] | K
sea surface salinity | [0,50] | PSU
sea ice concentration | [0, 100] | %

###  2.2 Preprocessing

To feed our data to LSTM model, we reshape our $N$x$11$ two-dimensional
datasets to $M$x$T$x$11$ three-dimensional datasets in such a manner that each
row of predictors corresponds to (M-1)$th$ month’s sea-ice value. Here N
represents total number of data samples, M represents total number of months
and T represents the timestep. We achieve this by removing the first row of
sea-ice values and Nth record from monthly and daily data, the details of
which are mentioned in sections below. In both the approaches, we rescale the
data using Standard Scaler normalization technique.

####  2.2.1 Daily Data

We first needed to reshape the daily data to add a third dimension in order to
get chunks of 30 XM-1 predictors corresponding to each YM predictand. For
this, we first removed the 31st days from specific months. Then we augmented
28th or 29th day of February once or twice depending upon the occurrence of
leap year. The final rows were perfect multiples of 30. We then reshaped the N
rows of 11 predictors to Mx30x11 3D matrix and removed the last Mth row to
align the dataset with $M-1$ monthly sea ice values. Here, 30 represents the
timestep T for one month’s data. With this arrangement, we get January 1979’s
data values against February 1979’s sea-ice extent value and so on.

####  2.2.2 Monthly Data

Since this version of data already corresponded to monthly sea-ice values, we
reshape the Mx11 data matrix to Mx1x11 data matrix. Here 1 represents timestep
T for one month. To incorporate lead time of 1, we remove last Mth record of
monthly data to align it with $M-1$ sea-ice values such as January 1979’s
monthly record corresponds to February 1979’s sea-ice value and so on.

###  2.3 Overall Architecture

We propose an attention-based ensemble method for multi-temporal LSTM modeling
to predict monthly sea ice extent with a lead time of 1 month. To cater the
two temporal frequencies of datasets, we first design two simple many-to-one
LSTM networks, daily LSTM or d-LSTM, and monthly LSTM or m-LSTM. We then
concatenate the results from these two branches with and without attention to
get monthly predictions for the sea-ice values. All three variants of models
are developed using Keras Functional API with Tensorflow backend, optimized
using ’Adam’ optimizer and evaluated using ’mean-squared-error’ loss. To avoid
over-training, the models are trained using the Early Stopping evaluation
criteria. The overall architecture of our attention-based ensemble method is
illustrated in Figure 1. Here, $D_{M-1}$ and $M-1$ corresponds to daily and
monthly records from preceding month and $Y_{M-1}$ represent sea-ice values
from preceding month whereas $Y_{M}$ represents predictions for the next
month. Here we are combining only two temporal models, owing to the
availability of two temporal datasets. However, the proposed architecture can
incorporate any number of Deep Learning models in its concatenation part; the
final fully connected layer learns weights to assign to individual models and
returns prediction based on those weights.

###  2.4 Daily-to-Monthly Prediction Network (d-LSTM)

We first designed a simple LSTM network with three LSTM layers, one Dropout
layer and two fully connected layers. This model takes in as input a three
dimensional array $N$x$T$x$P$ of daily data, where N is the batch size, T is
the timestep and P is the number of predictors. In our case, this setting is
equivalent to $M$x$30$x$11$. The main motivation behind developing this
network was to overcome the small-data problem faced by a deep learning model
that is trained on few hundreds of monthly data and predicts monthly sea-ice
values. We train this model on a dataset of 12,240 records, that is 34 years.
The corresponding prediction is the monthly means of sea-ice extent for
($M+1$)$th$ month. To our knowledge, combining lower temporal frequency data
to predict a higher temporal frequency value is still a novel approach in
data-driven atmospheric forecasting.

###  2.5 Monthly-to-Monthly Prediction Network (m-LSTM)

We then designed another simple LSTM network with the similar architecture as
d-LSTM. However, instead of a timestep of 30, this models takes in a timestep
of 1, representing one month. We train this model on the monthly dataset of
420 records, that is 34 years. Similar to d-LSTM, here the corresponding
predictand is the monthly mean of sea-ice extent for ($M+1$)$th$ month.

###  2.6 Attention-based Ensemble Model (EA-LSTM)

Attention Mechanism. Not all hidden states of recurrent neural network
contribute equally to the predictions. Inspired by attention mechanism
introduced in Luong et al. (2015), we add an intermediary self-attention layer
on top of the final LSTM layers in both d-LSTM and m-LSTM, in order to
identify which hidden states contribute more to the target prediction. The
attention mechanism assigns importance scores to the different hidden states
of LSTM model enabling the model to focus on most relevant features within the
input. Specifically, at each time step $t$, our attention layer first takes as
input the hidden states $h_{t}$ at the top layer of a stacking LSTM, it then
infers a context vector $c_{t}$ that captures relevant hidden information
based on current target state $h_{t}$ and all source states $h_{s}$ of the
LSTM model. Attention mechanism helps improve the deep learning model by
attending to relevant hidden states so that it can significantly reduces the
error of the prediction.

Ensemble Model. In all recent research work conducted on sea ice predictions,
we have seen models trained on same temporal frequency as their predictions.
However, in our case, m-LSTM itself cannot be a good predictive method for our
dataset due to its small volume. Since the monthly dataset suffers from small-
data problem, we combined the two approaches using an attention-based ensemble
technique. To ensemble the two temporal models, we retrieve the model output
from each of the fully connected layers of both LSTM networks to get the
individual model predictions. We then concatenate the predictions retrieved
from both LSTM branches and add a fully connected layer to learn the
concatenation weights of both the models give final monthly sea-ice
predictions. We give a generic formulation of our ensemble in Eq. 1 where y is
the final model outcome, $f_{1},..f_{n}$ represent the $N$ constituent inner
models and $w_{n}$ is the weight assigned to individual model. In our case,
$N=2$.

$p(y|f_{1},..f_{n})=\sum_{n=1}^{N}w_{n}f_{n}$ (1)

##  3 Results & Analysis

We present results from the experiments conducted on baseline models as well
as our proposed deep learning models. We present our analysis by comparing the
results from all experiments using the percentage RMSE loss and R-squared
score.

###  3.1 Baseline Experiments

To evaluate the comparative performance of our proposed model, we performed
sea-ice forecasting on monthly dataset with a lead time of 1 using five
renowned Machine Learning models enlisted in Table 2. All these models were
trained on first 34 years of data, that is, 420 records and tested on last 5
years, that is, 80 records. The results achieved from these models are
tabulated in Table 2. Among these baseline models, we see that both ensemble
models Random Forest and XGBoost have the highest prediction performance on
the monthly dataset.

Table 2: Experimental results from baseline (first five rows) and proposed
(last four rows) models on Sea Ice prediction with a lead time of 1 month.
Model |  $R^{2}$ Score | %RMSE
---|---|---
Linear Regression | 0.974 | 5.05
Decision Tree | 0.963 | 6.00
Random Forest | 0.978 | 4.63
XGBoost | 0.976 | 4.83
Polynomial Regression | 0.966 | 5.76
$d-$LSTM | 0.980 | 4.45
$m-$LSTM | 0.981 | 4.21
E-LSTM | 0.977 | 4.60
EA-LSTM | 0.982 | 4.11

Figure 2: Time-Series Plot of Sea Ice observational data, m-LSTM predictions
and EA-LSTM predictions for January 2014 - December 2018.

###  3.2 Comparative Analysis

We first evaluated the performance of simple d-LSTM and m-LSTM models. Through
our experiment, we see that d-LSTM gives promising predictions as it is
trained on daily data and predicts monthly mean sea ice values. We further
observed that m-LSTM not only out-performs d-LSTM but also provides
competitive results compared to multiple baseline models. We then evaluated
the performance of our ensemble method with and without attention and observed
that attention mechanism not only improved the overall performance but also
significantly reduced the model loss. A tabulated summary of these results can
be seen in Table 2. Comparing our results with the performance of similar
methods proposed by Chi & Kim (2017) and Kim et al. (2020), we see a
significant performance improvement in our sea-ice predictions with around
1.65% and 8% reduction in RMSE loss respectively, as compared to their
results.
Figure 2 shows the temporal predictions from m-LSTM and EA-LSTM against the
observed sea-ice values for the time period of January 2014 to December 2018.
Looking at the observed versus predicted graphs of sea-ice, we see that our
EA-LSTM method gives predictions that are more aligned with the observed
values; it also gives better predictions of sea-ice extent values in the
melting season of July-September as compared to simple m-LSTM, giving us more
confidence in the attention-based ensemble method.

##  4 Conclusion & Future Work

In this paper, we present an attention-based ensemble method to predict
monthly sea-ice values with a lead time of 1 month. Our proposed model can
combine models having different temporal resolutions and learn their weighted
average using attention-based mechanism. We started off with simple daily-to-
monthly and monthly-to-monthly prediction models and moved forward to develop
an ensemble model that learns from multi-temporal datasets and gives sea-ice
predictions with a commendable RMSE loss of 4.11%. Though we trained the
ensemble using only two model branches, our proposed architecture is
expandable to any number of model branches that can be trained on different
temporal resolutions. Through our experiments, we showed how attention
improves model performance and reduces overall loss. Comparing our results
with baseline models and related research work, we see our attention-based
ensemble technique gives promising results for forecasting monthly sea-ice
extent.

It should be noted that there are several limitations with current study.
First, the uncertainties in satellite retrieved sea ice observation and ERA-5
reanalysis product cannot be neglected, which will exert a large influence on
our results. In addition, the seasonality and inter-annual variability are not
well handled by the current method. In the future, we are going to apply the
same method to deseasonalized time series. In the meantime, the simulations
from different models will be used to better understand the impacts of inter-
annual variability on sea ice predictability.

For future work, we will also extend our proposed ensemble method to combine
spatio-temporal models with different spatial and temporal resolutions. We
also plan to visualize the attention weights learned from these intermediary
attention layers to better understand the underlying working of deep learning
models and to interpret what the ensemble model learns.

The 1-month sea ice forecast is our starting point. In the future, we will go
beyond the seasonal sea ice forecast and investigate how ensemble method can
help us to improve the long-term sea ice projection. The sea ice coverage and
length of open water season will inform future planning of military, civilian,
and commercial infrastructure including buildings and marine vessels. In the
meantime, we should also be aware of some potential risks with a more accurate
sea ice forecast (e.g., more aggressive resource extraction in the Arctic).
Nevertheless, this work will not only help us to better predict the future
climate, but also promote local communities and the broader international
society to respond and adapt to a changing Arctic with increased greenhouse
emissions.

## Acknowledgment

This work is supported by grants CAREER: Big Data Climate Causality Analytics
(OAC–1942714), REU Site: Online Interdisciplinary Big Data Analytics in
Science and Engineering (OAC–2050943), and CyberTraining: DSE: Cross-Training
of Researchers in Computing, Applied Mathematics and Atmospheric Sciences
using Advanced Cyberinfrastructure Resources (OAC–1730250) from the National
Science Foundation.

## References

  * Cavalieri et al. (1996) Cavalieri, D. J., Parkinson, C. L., Gloersen, P., and Zwally, H. J.  Sea ice concentrations from nimbus-7 smmr and dmsp ssm/i-ssmis passive microwave data, version 1.  1996\.  doi: https://doi.org/10.5067/8GQ8LZQVL0VL.
  * Chi & Kim (2017) Chi, J. and Kim, H.-c.  Prediction of arctic sea ice concentration using a fully data driven deep neural network.  _Remote Sensing_ , 9(12), 2017.  ISSN 2072-4292.  doi: 10.3390/rs9121305.  URL https://www.mdpi.com/2072-4292/9/12/1305.
  * Freedman et al. (2021) Freedman, A., Muyskens, J., and Samenow, J.  The historic cold snap and snow by the numbers.  _Washington Post_ , Feb 2021.  URL https://www.washingtonpost.com/weather/2021/02/24/texas-winter-storm-temperature-records/.
  * Holland & Bitz (2003) Holland, M. M. and Bitz, C. M.  Polar amplification of climate change in coupled models.  _Climate Dynamics_ , 21(3-4):221–232, 2003.
  * Holland et al. (2019) Holland, M. M., Landrum, L., Bailey, D., and Vavrus, S.  Changing seasonal predictability of arctic summer sea ice area in a warming climate.  _Journal of Climate_ , 32(16):4963–4979, 2019\.
  * Kim et al. (2019) Kim, J., Kim, K., Cho, J., Kang, Y. Q., Yoon, H.-J., and Lee, Y.-W.  Satellite-based prediction of arctic sea ice concentration using a deep neural network with multi-model ensemble.  _Remote Sensing_ , 11(1), 2019.  ISSN 2072-4292.  doi: 10.3390/rs11010019.  URL https://www.mdpi.com/2072-4292/11/1/19.
  * Kim et al. (2020) Kim, Y. J., Kim, H.-C., Han, D., Lee, S., and Im, J.  Prediction of monthly arctic sea ice concentrations using satellite and reanalysis data based on convolutional neural networks.  _The Cryosphere_ , 14(3):1083–1104, 2020.  doi: 10.5194/tc-14-1083-2020.  URL https://tc.copernicus.org/articles/14/1083/2020/.
  * Liu et al. (2021) Liu, Q., Zhang, R., Wang, Y., Yan, H., and Hong, M.  Daily prediction of the arctic sea ice concentration using reanalysis data based on a convolutional lstm network.  _Journal of Marine Science and Engineering_ , 9(3), 2021\.  ISSN 2077-1312.  doi: 10.3390/jmse9030330.  URL https://www.mdpi.com/2077-1312/9/3/330.
  * Luong et al. (2015) Luong, T., Pham, H., and Manning, C. D.  Effective approaches to attention-based neural machine translation.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pp. 1412–1421. Association for Computational Linguistics, September 2015.
  * Notz & Stroeve (2018) Notz, D. and Stroeve, J.  The trajectory towards a seasonally ice-free arctic ocean.  _Current climate change reports_ , 4(4):407–416, 2018.
  * Serreze & Stroeve (2015) Serreze, M. C. and Stroeve, J.  Arctic sea ice trends, variability and implications for seasonal ice forecasting.  _Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences_ , 373(2045):20140159, 2015.  doi: 10.1098/rsta.2014.0159.  URL https://royalsocietypublishing.org/doi/abs/10.1098/rsta.2014.0159.
  * Wang et al. (2017) Wang, L., Scott, K. A., and Clausi, D. A.  Sea ice concentration estimation during freeze-up from sar imagery using a convolutional neural network.  _Remote Sensing_ , 9(5), 2017.  ISSN 2072-4292.  doi: 10.3390/rs9050408.  URL https://www.mdpi.com/2072-4292/9/5/408.