Quantum estimation bound of Gaussian matrix permanent

Understand

Exact calculation and even multiplicative error estimation of matrix permanent are challenging for both classical and quantum computers.

• Regarding the permanents of random Gaussian matrices, the additive error estimation is closely linked to boson sampling, and achieving multiplicative error estimation requires exponentially many samplings.
• Our newly developed formula for matrix permanents and its corresponding quantum expression have enabled better estimation of the average additive error for random Gaussian matrices compared to Gurvits' classical sampling algorithm.
• The well-known Ryser formula has been converted into a quantum permanent estimator.