Fast Quantum Algorithms for Trace Distance Estimation

Wang, Q; Zhang, Z

Fast Quantum Algorithms for Trace Distance Estimation

Wang, Q Zhang, Z

Permalink

Publisher:: Institute of Electrical and Electronics Engineers (IEEE)
Publication Type:: Journal Article
Citation:: IEEE Transactions on Information Theory, 2023, PP, (99), pp. 1-1
Issue Date:: 2023-01-01

Embargoed

	Filename	Description	Size
	Fast Quantum Algorithms for Trace Distance Estimation.pdf	Accepted version	333.75 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Embargoed
Open Access

This item is currently unavailable due to the publisher's embargo.

The embargo period expires on 2 Oct 2025

Full metadata record

Field	Value	Language
dc.contributor.author	Wang, Q
dc.contributor.author	Zhang, Z https://orcid.org/0000-0002-7436-0426
dc.date.accessioned	2024-03-15T01:55:49Z
dc.date.available	2024-03-15T01:55:49Z
dc.date.issued	2023-01-01
dc.identifier.citation	IEEE Transactions on Information Theory, 2023, PP, (99), pp. 1-1
dc.identifier.issn	0018-9448
dc.identifier.issn	1557-9654
dc.identifier.uri	http://hdl.handle.net/10453/176755
dc.description.abstract	In quantum information, trace distance is a basic metric of distinguishability between quantum states. However, there is no known efficient approach to estimate the value of trace distance in general. In this paper, we propose efficient quantum algorithms for estimating the trace distance within additive error ε between mixed quantum states of rank <italic>r</italic>. Specifically, we first provide a quantum algorithm using <italic>r</italic> · Õ(1/ε2) queries to the quantum circuits that prepare the purifications of quantum states. Then, we modify this quantum algorithm to obtain another algorithm using Õ (<italic>r</italic>2/ε5) samples of quantum states, which can be applied to quantum state certification. These algorithms have query/sample complexities that are independent of the dimension <italic>N</italic> of quantum states, and their time complexities only incur an extra <italic>O</italic>(log(<italic>N</italic>)) factor. In addition, we show that the decision version of low-rank trace distance estimation is BQP-complete.
dc.language	en
dc.publisher	Institute of Electrical and Electronics Engineers (IEEE)
dc.relation.ispartof	IEEE Transactions on Information Theory
dc.relation.isbasedon	10.1109/TIT.2023.3321121
dc.rights	info:eu-repo/semantics/embargoedAccess
dc.subject	0801 Artificial Intelligence and Image Processing, 0906 Electrical and Electronic Engineering, 1005 Communications Technologies
dc.subject.classification	Networking & Telecommunications
dc.subject.classification	4006 Communications engineering
dc.subject.classification	4613 Theory of computation
dc.title	Fast Quantum Algorithms for Trace Distance Estimation
dc.type	Journal Article
utslib.citation.volume	PP
utslib.for	0801 Artificial Intelligence and Image Processing
utslib.for	0906 Electrical and Electronic Engineering
utslib.for	1005 Communications Technologies
pubs.organisational-group	University of Technology Sydney
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	embargoed	*
utslib.copyright.embargo	2025-10-02T00:00:00+1000Z
dc.date.updated	2024-03-15T01:55:48Z
pubs.issue	99
pubs.publication-status	Published
pubs.volume	PP
utslib.citation.issue	99

Abstract:

In quantum information, trace distance is a basic metric of distinguishability between quantum states. However, there is no known efficient approach to estimate the value of trace distance in general. In this paper, we propose efficient quantum algorithms for estimating the trace distance within additive error ε between mixed quantum states of rank r. Specifically, we first provide a quantum algorithm using r · Õ(1/ε2) queries to the quantum circuits that prepare the purifications of quantum states. Then, we modify this quantum algorithm to obtain another algorithm using Õ (r2/ε5) samples of quantum states, which can be applied to quantum state certification. These algorithms have query/sample complexities that are independent of the dimension N of quantum states, and their time complexities only incur an extra O(log(N)) factor. In addition, we show that the decision version of low-rank trace distance estimation is BQP-complete.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/176755