Complexity phase transitions in instantaneous quantum polynomial-time circuits
We study the classical hardness of learning the output distribution from instantaneous quantum polynomial-time circuits with a varying density of two-qubit gates. We first investigate the complexity phases relevant to simulating the output distribution. In addition to a known parameter regime for an...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2025-01-01
|
| Series: | Physical Review Research |
| Online Access: | http://doi.org/10.1103/PhysRevResearch.7.013001 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850088911580168192 |
|---|---|
| author | Chae-Yeun Park Michael J. Kastoryano |
| author_facet | Chae-Yeun Park Michael J. Kastoryano |
| author_sort | Chae-Yeun Park |
| collection | DOAJ |
| description | We study the classical hardness of learning the output distribution from instantaneous quantum polynomial-time circuits with a varying density of two-qubit gates. We first investigate the complexity phases relevant to simulating the output distribution. In addition to a known parameter regime for anticoncentration, where the classical simulation is believed to be infeasible, we identify a novel parameter condition such that the classically simulability of the circuit can be proven rigorously. Next, we explore the classical learnability of the output distribution. We prove that a circuit instance whose output distribution is not classically learnable exists, assuming the hardness of learning parity with noise. We numerically study this phenomenon deeply using a classical energy-based model, where we find that the classical model fails to learn the output distribution even when the density of two-qubit gates is much smaller than that for the anticoncentration. We argue that this is mainly due to the fact that an accurate classical description of the output distribution requires exponentially large amount of resources. |
| format | Article |
| id | doaj-art-139d27ddf0bb49c4badd98d4b3f61ea3 |
| institution | DOAJ |
| issn | 2643-1564 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | Physical Review Research |
| spelling | doaj-art-139d27ddf0bb49c4badd98d4b3f61ea32025-08-20T02:42:56ZengAmerican Physical SocietyPhysical Review Research2643-15642025-01-017101300110.1103/PhysRevResearch.7.013001Complexity phase transitions in instantaneous quantum polynomial-time circuitsChae-Yeun ParkMichael J. KastoryanoWe study the classical hardness of learning the output distribution from instantaneous quantum polynomial-time circuits with a varying density of two-qubit gates. We first investigate the complexity phases relevant to simulating the output distribution. In addition to a known parameter regime for anticoncentration, where the classical simulation is believed to be infeasible, we identify a novel parameter condition such that the classically simulability of the circuit can be proven rigorously. Next, we explore the classical learnability of the output distribution. We prove that a circuit instance whose output distribution is not classically learnable exists, assuming the hardness of learning parity with noise. We numerically study this phenomenon deeply using a classical energy-based model, where we find that the classical model fails to learn the output distribution even when the density of two-qubit gates is much smaller than that for the anticoncentration. We argue that this is mainly due to the fact that an accurate classical description of the output distribution requires exponentially large amount of resources.http://doi.org/10.1103/PhysRevResearch.7.013001 |
| spellingShingle | Chae-Yeun Park Michael J. Kastoryano Complexity phase transitions in instantaneous quantum polynomial-time circuits Physical Review Research |
| title | Complexity phase transitions in instantaneous quantum polynomial-time circuits |
| title_full | Complexity phase transitions in instantaneous quantum polynomial-time circuits |
| title_fullStr | Complexity phase transitions in instantaneous quantum polynomial-time circuits |
| title_full_unstemmed | Complexity phase transitions in instantaneous quantum polynomial-time circuits |
| title_short | Complexity phase transitions in instantaneous quantum polynomial-time circuits |
| title_sort | complexity phase transitions in instantaneous quantum polynomial time circuits |
| url | http://doi.org/10.1103/PhysRevResearch.7.013001 |
| work_keys_str_mv | AT chaeyeunpark complexityphasetransitionsininstantaneousquantumpolynomialtimecircuits AT michaeljkastoryano complexityphasetransitionsininstantaneousquantumpolynomialtimecircuits |