Editing Compressed Sensing Tomography

In this [https://arxiv.org/abs/1205.2300 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 <math>n</math> qubits, with the dimension to be <math>d = 2^n</math>
* 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==

* <math>n</math>: number of qubits in the system
* <math>d</math>: Dimension of the Hilbert space. <math>d = 2^n</math>
* <math>\mathcal{P}</math>: Set of all <math>d^2</math> Pauli operators.
* <math>P</math>: Pauli operator in <math>\mathcal{P}</math>. <math>P = \sigma_1 \otimes ... \otimes \sigma_n</math>
* <math>\sigma_i</math>: This belongs to the set of Pauli matrices <math>\{I, \sigma^x, \sigma^y, \sigma^z\}</math>
* <math>m</math>: Selected number of Pauli operators. <math>m = O((rd) log d)</math>
* <math>\rho</math>: unknown quantum state
* <math>t</math>: total number of copies of <math>\rho</math>. <math>t = O((\frac{rd}{\epsilon})^2 log d)</math>, <math>r</math> is the unknown rank and <math>\epsilon</math> is the accuracy in the trace distance
* <math>\mathcal{A}</math>: Sampling operator which is a linear map defined for all <math>i \in [m]</math>. Normalisation is chosen because <math>\mathbb{E}\mathcal{A}^*\mathcal{A} = I</math>
* <math>\mathbb{E}</math>: expectation value of a random variable
* <math>z</math>: statistical noise due to the finite number of samples, or even due to an adversary
* <math>y</math>: Vector to describe the measurement procedure
* <math>X</math>: Matrix that fits data <math>y</math>
* <math>\rho_{DS}</math>: Estimate for the matrix using matrix Dantzig selector
* <math>\lambda</math>:  Parameter for trace minimisation which is set according to the noise in the data
* <math>\rho_{Lasso}</math>: Estimate for the matrix using matrix Lasso
* <math>\mu</math>: regularization parameter which is set according to the noise level
* <math>C_0, C_1, C^{'}_0, C^{'}_1</math>: fixed absolute constants
* <math>\rho_c</math>:  For any quantum state <math>\rho</math>, we write <math>\rho = \rho_c + \rho_r</math> where <math>\rho_r</math> is the best rank-r approximation to <math>\rho</math> and <math>\rho_c</math> is the residual part.

==Properties==

* Figure of merit: Density Matrix of the quantum state
* A random subset of <math>m = O((rd) </math>log<math> d) </math> Pauli observables are used in this method. The sample complexity of compressed tomography is nearly independent of the number of measurement settings <math>m</math>, so long as <math>m \geq O(rd</math> poly log <math>d)</math>.
* The accuracy of the compressed sensing estimates are fairly insensitive to the number of measurement settings <math>m</math>  So by choosing <math>m << d^2</math> one still obtains accurate estimates, but with much faster classical post-processing, since the size of the data set scales like <math>O(m)</math> rather than <math>O(d^2)</math>
* This method uses <math>t = O((\frac{rd}{\epsilon})^2 </math>log<math> d)</math> 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 <math>O(rd</math> poly log <math>d)</math> Pauli measurements, that has the ability to reconstruct every rank-<math>r</math> <math>d</math>×<math>d</math> 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-<math>r</math> states using adaptive sequences of single-copy Pauli measurements is at least <math>O(r^2 d^2 / </math>log <math>d)</math>  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, <math>\rho</math>

* Consider system of <math>n</math> qubits and dimension <math>d = 2^n</math>
* Define <math>\mathcal{P}</math> and select <math>m</math> operators <math>(P_1, ... , P_m)</math> from <math>\mathcal{P}</math>
* Make <math>t</math> copies of the unknown quantum state <math>\rho</math>
* For <math>i = 1, 2, ..., m</math>:
** For <math>j = 1, 2, ..., t/m</math>:
*** Measure <math>P_i</math> on <math>\rho</math>
** Average measurement results to get <math>Tr(P_i\rho)</math>
** Define sampling operator <math>\mathcal{A}, \mathcal{A}(\rho)_i = \sqrt{\frac{d}{m}} Tr(P_i\rho)</math>
* Output of measurements is defined as the vector <math>y = \mathcal{A}(\rho) + z</math>
* To estimate <math>\rho</math> there are two methods:
** Using trace minimization:
*** Choose <math>\lambda</math> such that <math> ||A^*(z)|| \leq \lambda</math>, then <math>||\hat{\rho}_{DS} -\rho||_{tr} \leq C_0r\lambda + C_1||\rho_c||_{tr}</math>
*** <math>\hat{\rho}_{DS} =</math> argmin<math>_X ||X||_{tr}</math> such that <math>||\mathcal{A}^*(\mathcal{A}(X) - y)|| \leq \lambda</math>
** Using least-squares linear regression with trace-norm regularization:
*** Choose <math>\mu</math> such that <math>||A^*(z)|| \leq \mu</math>, then <math>||\hat{\rho}_{Lasso} -\rho||_{tr} \leq C^{'}_0r\lambda + C^{'}_1||\rho_c||_{tr}</math>
*** <math>\hat{\rho}_{Lasso} =</math> argmin<math>_X \frac{1}{2} ||\mathcal{A}(X)-y||_2^2 + \mu||X||_{tr}</math>

==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 [https://arxiv.org/abs/1205.2300 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 <math>m = O(rd^2 </math>log<math> d)</math> 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

<div style='text-align: right;'>''*contributed by Rhea Parekh''</div>