Compressed Sensing Tomography

In this example protocol quantum state tomography is performed using compressed sensing method. This method is specialized for quantum states that are fairly pure and they offer a significant performance improvement on large quantum systems. A low-density matrix can be estimated using fewer copies of the state and hence the sample complexity of the tomography decreases with the rank. Unknown low-rank states can also be reconstructed from an incomplete set of measurements using matrix completion techniques. This method is less resource expensive and more reliable recovery is possible based on the same type of randomly chosen measurements compared to full tomography.

Tags: Certification protocol, Tomography, Quantum State density matrix reconstruction, compressed sensing

Assumptions

• The scheme is robust to noise and continues to perform well when the measurements are imprecise or when the state is only close to a low-rank state.
• A binomial noise model is assumed in this method, but minor modifications could extend this result to other relevant noise models, such as multinomial, Gaussian, or Poissonian noise.
• Multiple copies of the final quantum state are available.

Outline

This technique concentrates on the states that are well approximated by density matrices of rank less than the dimension. This approach can be applied to many realistic experimental situations, where the ideal state of the system is pure, and physical constraints ensure that the actual noisy state still has low entropy. Compressed sensing tomography involves two steps, measuring an incomplete set of observables and using trace minimization or regularization to reconstruct low-rank solutions. The goal of this method is to reconstruct a low-rank state using as few samples as possible.

There are two different methods used to determine the density matrix of the unknown quantum state. The first estimator is obtained by constrained trace minimisation and the second estimator is obtained by least-squares linear regression with trace-norm regularization.

The method describes the measurement procedure first and then the density matrix reconstruction process is described. This method consists of the following steps:

• Consider a system of $n$ qubits, with the dimension to be Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d = 2^n}
• Form a set of Pauli operators using Pauli matrices.
• Choose a particular number of Pauli operators by sampling uniformly and independently at random from the set formed in the set above. (Alternatively, one can choose these Pauli operators randomly without replacement)
• For each of the Pauli operator selected in step 3, use a particular number of copies of the unknown quantum state, and for each of this quantum state measure the selected Pauli operator. Average the measurement outcomes over all copies of the unknown quantum state to obtain an estimate of the expectation value. The number of selected copies of the quantum state and the number of the selected Pauli operators from the set are dependent on the dimension and the rank of the density matrix. A sampling operator is defined here using the expectation value after normalising it.
• The output of the measurement procedure is then described as a linear vector which also takes the statistical noise due to the finite number of samples, or even due to an adversary into consideration.
• To estimate the density matrix of the quantum state, one of the two methods: constrained trace minimisation (a.k.a. the matrix Dantzig selector) or least-squares linear regression with trace-norm regularization (a.k.a. the matrix Lasso) can be used. Both of these methods are based on the intuition of finding the density matrix which fits the measurement data while minimizing the trace norm of that matrix, which serves as a surrogate for minimising the rank of that matrix.

Hardware Requirements

• Trusted Measurement device.

Notation

• $n$: number of qubits in the system
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} : Dimension of the Hilbert space. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d = 2^n}
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{P}} : Set of all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d^2} Pauli operators.
• $P$: Pauli operator in ${\mathcal {P}}$. $P=\sigma _{1}\otimes ...\otimes \sigma _{n}$
• $\sigma _{i}$: This belongs to the set of Pauli matrices $\{I,\sigma ^{x},\sigma ^{y},\sigma ^{z}\}$
• $m$: Selected number of Pauli operators. $m=O((rd)logd)$
• $\rho$: unknown quantum state
• $t$: total number of copies of $\rho$. $t=O(({\frac {rd}{\epsilon }})^{2}logd)$, $r$ is the unknown rank and $\epsilon$ is the accuracy in the trace distance
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{A}} : Sampling operator which is a linear map defined for all $i\in [m]$. Normalisation is chosen because Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{E}\mathcal{A}^*\mathcal{A} = I}
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{E}} : expectation value of a random variable
• $z$: statistical noise due to the finite number of samples, or even due to an adversary
• $y$: Vector to describe the measurement procedure
• $X$: Matrix that fits data $y$
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho_{DS}} : Estimate for the matrix using matrix Dantzig selector
• $\lambda$: Parameter for trace minimisation which is set according to the noise in the data
• $\rho _{Lasso}$: Estimate for the matrix using matrix Lasso
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu} : regularization parameter which is set according to the noise level
• $C_{0},C_{1},C_{0}^{'},C_{1}^{'}$: fixed absolute constants
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho_c} : For any quantum state $\rho$, we write $\rho =\rho _{c}+\rho _{r}$ where $\rho _{r}$ is the best rank-r approximation to $\rho$ and $\rho _{c}$ is the residual part.

Properties

• Figure of merit: Density Matrix of the quantum state
• A random subset of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m = O((rd) } log$d)$ Pauli observables are used in this method. The sample complexity of compressed tomography is nearly independent of the number of measurement settings Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} , so long as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m \geq O(rd} poly log Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d)} .
• The accuracy of the compressed sensing estimates are fairly insensitive to the number of measurement settings Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} So by choosing Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m << d^2} one still obtains accurate estimates, but with much faster classical post-processing, since the size of the data set scales like Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(m)} rather than Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(d^2)}
• This method uses Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t = O((\frac{rd}{\epsilon})^2 } logFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d)} copies of the unknown quantum state.
• Compressed tomography provides better accuracy at a reduced computational cost compared to standard maximum-likelihood estimation
• This method works on the “universal” method for low-rank matrix recovery, which states that there exists a fixed set of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(rd} poly log Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d)} Pauli measurements, that has the ability to reconstruct every rank-Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} ×Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} matrix. With a high probability, a random choice of Pauli measurements will achieve this.
• when the unknown matrix ρ is full rank, our method returns a (certifiable) rank-r approximation of ρ, that is almost as good as the best such approximation
• The information-theoretic lower bound for tomography of rank-Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r} states using adaptive sequences of single-copy Pauli measurements is at least Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O(r^2 d^2 / } log Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d)} copies are needed to obtain an estimate with constant accuracy in the trace distance. The upper bound on the sample complexity of compressed tomography is nearly tight, and compressed tomography nearly achieves the optimal sample complexity among all possible methods using Pauli measurements.

Procedure Description

Input: copies of unknown quantum state

Output: Density matrix of the quantum state, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho}

• Consider system of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} qubits and dimension Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d = 2^n}
• Define Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{P}} and select Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m} operators Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (P_1, ... , P_m)} from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{P}}
• Make Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t} copies of the unknown quantum state Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho}
• For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i = 1, 2, ..., m} :
  • For Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j = 1, 2, ..., t/m} :
    • Measure Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P_i} on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho}
  • Average measurement results to get Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Tr(P_i\rho)}
  • Define sampling operator Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{A}, \mathcal{A}(\rho)_i = \sqrt{\frac{d}{m}} Tr(P_i\rho)}
• Output of measurements is defined as the vector Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y = \mathcal{A}(\rho) + z}
• To estimate Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho} there are two methods:
  • Using trace minimization:
    • Choose Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ||A^*(z)|| \leq \lambda} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ||\hat{\rho}_{DS} -\rho||_{tr} \leq C_0r\lambda + C_1||\rho_c||_{tr}}
    • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{\rho}_{DS} =} argminFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle _X ||X||_{tr}} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ||\mathcal{A}^*(\mathcal{A}(X) - y)|| \leq \lambda}
  • Using least-squares linear regression with trace-norm regularization:
    • Choose Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ||A^*(z)|| \leq \mu} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle ||\hat{\rho}_{Lasso} -\rho||_{tr} \leq C^{'}_0r\lambda + C^{'}_1||\rho_c||_{tr}}
    • Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \hat{\rho}_{Lasso} =} argminFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle _X \frac{1}{2} ||\mathcal{A}(X)-y||_2^2 + \mu||X||_{tr}}

Further Information

• Direct Fidelity Estimation can be further generalised to work with low-rank states. Thus, one can use compressed sensing tomography to get an estimated density matrix and use Direct fidelity estimation to check whether this state agrees with the true state. This check is guaranteed to be sound, even if the true state is not approximately low rank. Hence this is used to certify the state.
• Compressed sensing tomography (as mentioned in Steven T. Flammia et al) can also be applied to Quantum Process tomography. This method would have an advantage when the unknown quantum process has a small Kraus rank (only be expressed with a few Kraus operators). This occurs, for example, when the unknown process consists of unitary evolution combined with local noise (acting on each qubit individually, or acting on small subsets of the qubits). The process here can be characterised in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m = O(rd^2 } logFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d)} settings

Related Papers

• Steven T. Flammia et al arXiv:1205.2300: Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• David Gross et al arXiv:0909.3304: Quantum state tomography via compressed sensing

*contributed by Rhea Parekh