Related Experiment Video
Updated: Jan 26, 2026
08:04
Excitonic Hamiltonians for Calculating Optical Absorption Spectra and Optoelectronic Properties of Molecular Aggregates and Solids
Published on: May 27, 2020
8.9K
On the computational complexity of curing non-stoquastic Hamiltonians
Milad Marvian1,2,3, Daniel A Lidar4,5,6,7, Itay Hen5,6,8
1Research Laboratory of Electronics, Massachusetts Institute of Technology, Cambridge, MA, 02139, USA. mmarvian@mit.edu.
Nature Communications
|April 7, 2019
Summary
Transforming non-stoquastic Hamiltonians to be sign-problem-free is computationally hard. Finding such transformations, limited to single-qubit operations, is proven to be NP-complete, impacting quantum many-body simulations.
Area of Science:
- Quantum Computing
- Computational Complexity Theory
- Condensed Matter Physics
Background:
- Non-stoquastic Hamiltonians in quantum many-body systems cause the sign problem.
- The sign problem severely limits the efficiency of Quantum Monte Carlo (QMC) algorithms.
- Simulating these systems is crucial for understanding complex quantum phenomena.
Purpose of the Study:
- To investigate the computational complexity of 'curing' non-stoquastic Hamiltonians.
- To determine the difficulty of transforming non-stoquastic Hamiltonians into sign-problem-free ones.
- To analyze the implications of these transformations on quantum simulation.
Main Methods:
- Studying the computational complexity of Hamiltonian transformations.
- Proving NP-completeness for specific classes of transformations.
- Analyzing transformations restricted to single-qubit Clifford group elements and orthogonal matrices.
Main Results:
- The problem of finding a 'curing' transformation is NP-complete.
- This holds true when transformations are restricted to single-qubit Clifford group elements.
- The result also applies to transformations using general single-qubit orthogonal matrices.
Conclusions:
- Efficiently solving the sign problem for non-stoquastic Hamiltonians is computationally challenging.
- The NP-completeness result suggests fundamental limitations for certain quantum simulation techniques.
- Understanding these complexities is vital for advancing quantum many-body simulations.
Related Concept Videos
01:20Curing of Concrete
362
The hydration of cement takes place within the water-filled capillary pores. However, environmental elements can disrupt this process by evaporating water from the concrete surfaces. Sealed concrete with a water-cement ratio below 0.5 experiences self-desiccation, leading to water loss. The water loss in concrete is mitigated by curing. This technique involves keeping the concrete saturated to maintain the necessary temperature and moisture conditions, to optimally fill the spaces in the cement...
362
01:26Curing Methods
290
Concrete members with a small surface-to-volume ratio are cured by oiling and moistening the forms before casting the concrete member. These forms can be left in place for a prolonged period to prevent moisture loss, and can be wetted if made of a material suitable for wetting. If the forms are removed early, the concrete member is moistened and covered with polythene sheets to maintain moisture. For large horizontal concrete surfaces exposed to dry weather, a temporary covering is suspended...
290
01:25Accelerated Curing of Concrete
462
Accelerating concrete curing is achieved by applying heat and additional moisture. This process accelerates the hydration of the cement, resulting in an earlier strength gain in the concrete. Steam curing is a method wherein the concrete products are either transported through a chamber on a conveyor belt or encased in plastic, allowing steam at atmospheric pressure to circulate freely around them. This process begins with a phase of moist curing that typically lasts between 3 to 5 hours, after...
462
01:10Computed Tomography
8.1K
Tomography refers to imaging by sections. Computed tomography (CT) is a non-invasive imaging technique that uses computers to analyze several cross-sectional X-rays to reveal minute details about structures in the body.
The technique was invented in the 1970s and is based on the principle that as X-rays pass through the body, they are absorbed or reflected at different levels. In the technique, a patient lies on a motorized platform while a computerized axial tomography (CAT) scanner rotates...
The technique was invented in the 1970s and is based on the principle that as X-rays pass through the body, they are absorbed or reflected at different levels. In the technique, a patient lies on a motorized platform while a computerized axial tomography (CAT) scanner rotates...
8.1K
02:41Protein Complex Assembly
16.7K
Proteins can form homomeric complexes with another unit of the same protein or heteromeric complexes with different types. Most protein complexes self-assemble spontaneously via ordered pathways, while some proteins need assembly factors that guide their proper assembly. Despite the crowded intracellular environment, proteins usually interact with their correct partners and form functional complexes.
Many viruses self-assemble into a fully functional unit using the infected host cell to...
Many viruses self-assemble into a fully functional unit using the infected host cell to...
16.7K
01:57Protein Complexes with Interchangeable Parts
2.9K
Groups of proteins may form a complex where each protein in this complex has a different role in the overall execution of the complex’s function. Often some of the proteins in the complex can be replaced by a closely related variant to give a complex that contains many of the same components yet is functionally distinct.
The SCF ubiquitin ligase is a protein complex of five individual proteins. This complex attaches ubiquitin to other target proteins to mark them for degradation. In order...
The SCF ubiquitin ligase is a protein complex of five individual proteins. This complex attaches ubiquitin to other target proteins to mark them for degradation. In order...
2.9K