Skip to main content

NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.

Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.

U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Simulating Concordant Computations

Published

Author(s)

Bryan K. Eastin

Abstract

A quantum state is called concordant if it has zero quantum discord with respect to any part. By extension, a concordant computation is one such that the state of the computer, at each time step, is concordant. In this paper, I describe a classical algorithm that, given a product state as input, permits the efficient simulation of any concordant quantum computation composed of gates acting on two or fewer qubits. This shows that a quantum computation composed of two-qubit gates must generate quantum discord if it is to efficiently solve a problem that requires super-polynomial time classically. While I employ the restriction to two-qubit gates sparingly, a crucial component of the simulation algorithm appears not to be extensible to gates acting on higher dimensional systems.
Citation
Physical Review A (Atomic, Molecular and Optical Physics)

Keywords

concordant computations, discord, simulation, two-qubit

Citation

Eastin, B. (2010), Simulating Concordant Computations, Physical Review A (Atomic, Molecular and Optical Physics), [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=904877 (Accessed October 16, 2025)

Issues

If you have any questions about this publication or are having problems accessing it, please contact [email protected].

Created June 23, 2010, Updated February 19, 2017
Was this page helpful?