An official website of the United States government
We define a map from an arbitrary quantum circuit to a local Hamiltonian whose ground state encodes the quantum computation. All previous maps relied on the Feynman-Kitaev construction, which introduces an ancillary ‘clock register’ to track the computational steps. Our construction, on the other hand, relies on injective tensor networks with associated parent Hamiltonians, avoiding the introduction of a clock register. This comes at the cost of the ground state containing only a noisy version of the quantum computation, with independent stochastic noise. We can remedy this—making our construction robust—by using quantum fault tolerance. In addition to the stochastic noise, we show that any state with energy density exponentially small in the circuit depth encodes a noisy version of the quantum computation with adversarial noise. We also show that any ‘combinatorial state’ with energy density polynomially small in depth encodes the quantum computation with adversarial noise. This serves as evidence that any state with energy density polynomially small in depth has a similar property. As an application, we show that contracting injective tensor networks to additive error is BQP-hard. We also discuss the implication of our construction to the quantum PCP conjecture, combining with an observation that QMA verification can be done in logarithmic depth.
more »
« less
Variational quasi-harmonic maps for computing diffeomorphisms
Computation of injective (or inversion-free) maps is a key task in geometry processing, physical simulation, and shape optimization. Despite being a longstanding problem, it remains challenging due to its highly nonconvex and combinatoric nature. We propose computation ofvariational quasi-harmonic mapsto obtain smooth inversion-free maps. Our work is built on a key observation about inversion-free maps: A planar map is a diffeomorphism if and only if it is quasi-harmonic and satisfies a special Cauchy boundary condition. We hence equate the inversion-free mapping problem to an optimal control problem derived from our theoretical result, in which we search in the space of parameters that define an elliptic PDE. We show that this problem can be solved by minimizing within a family of functionals. Similarly, our discretized functionals admit exactly injective maps as the minimizers, empirically producing inversion-free discrete maps of triangle meshes. We design efficient numerical procedures for our problem that prioritize robust convergence paths. Experiments show that on challenging examples our methods can achieve up to orders of magnitude improvement over state-of-the-art, in terms of speed or quality. Moreover, we demonstrate how to optimize a generic energy in our framework while restricting to quasi-harmonic maps.
more »
« less
- Award ID(s):
- 1838071
- PAR ID:
- 10601600
- Publisher / Repository:
- Association for Computing Machinery (ACM)
- Date Published:
- Journal Name:
- ACM Transactions on Graphics
- Volume:
- 42
- Issue:
- 4
- ISSN:
- 0730-0301
- Format(s):
- Medium: X Size: p. 1-26
- Size(s):
- p. 1-26
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Givenndisjoint intervals on together withnfunctions , , and an matrix , the problem is to find anL2solution , , to the linear system , where , is a matrix of finite Hilbert transforms with defined on , and is a matrix of the corresponding characteristic functions on . Since we can interpret , as a generalized multi‐interval finite Hilbert transform, we call the formula for the solution as “the inversion formula” and the necessary and sufficient conditions for the existence of a solution as the “range conditions”. In this paper we derive the explicit inversion formula and the range conditions in two specific cases: a) the matrix Θ is symmetric and positive definite, and; b) all the entries of Θ are equal to one. We also prove the uniqueness of solution, that is, that our transform is injective. In the case a), that is, when the matrix Θ is positive definite, the inversion formula is given in terms of the solution of the associated matrix Riemann–Hilbert Problem. In the case b) we reduce the multi interval problem to a problem onncopies of and then express our answers in terms of the Fourier transform. We also discuss other cases of the matrix Θ.more » « less
-
We proposequasi-harmonic weightsfor interpolating geometric data, which are orders of magnitude faster to compute than state-of-the-art. Currently, interpolation (or, skinning) weights are obtained by solving large-scale constrained optimization problems with explicit constraints to suppress oscillative patterns, yielding smooth weights only after a substantial amount of computation time. As an alternative, our weights are obtained as minima of an unconstrained problem that can be optimized quickly using straightforward numerical techniques. We consider weights that can be obtained as solutions to a parameterized family of second-order elliptic partial differential equations. By leveraging the maximum principle and careful parameterization, we pose weight computation as an inverse problem of recovering optimal anisotropic diffusivity tensors. In addition, we provide a customized ADAM solver that significantly reduces the number of gradient steps; our solver only requires inverting tens of linear systems that share the same sparsity pattern. Overall, our approach achieves orders of magnitude acceleration compared to previous methods, allowing weight computation in near real-time.more » « less
-
Abstract We prove that if is the mapping torus group of an injective endomorphism of a free group (of possibly infinite rank), then every two‐generator subgroup of is either free or a (finitary) sub‐mapping torus. As an application we show that if is a fully irreducible atoroidal automorphism, then every two‐generator subgroup of is either free or has finite index in .more » « less
-
Lattice thermal conductivity (κL) is a crucial characteristic of crystalline solids with significant implications for thermal management, energy conversion, and thermal barrier coating. The advancement of computational tools based on density functional theory (DFT) has enabled the effective utilization of phonon quasi-particle-based approaches to unravel the underlying physics of various crystalline systems. While the higher order of anharmonicity is commonly used for explaining extraordinary heat transfer behaviors in crystals, the impact of exchange-correlation (XC) functionals in DFT on describing anharmonicity has been largely overlooked. The XC functional is essential for determining the accuracy of DFT in describing interactions among electrons/ions in solids and molecules. However, most XC functionals in solid-state physics are primarily focused on computing the properties that only require small atomic displacements from the equilibrium (within the harmonic approximation), such as harmonic phonons and elastic constants, while anharmonicity involves larger atomic displacements. Therefore, it is more challenging for XC functionals to accurately describe atomic interactions at the anharmonicity level. In this study, we systematically investigate the room-temperature κL of 16 binary compounds with rocksalt and zincblende structures using var- ious XC functionals such as local density approximation (LDA), Perdew-Burke-Ernzerhof (PBE), revised PBE for solid and surface (PBEsol), optimized B86b functional (optB86b), revised Tao-Perdew-Staroverov-Scuseria (revTPSS), strongly constrained and appropriately normed functional (SCAN), regularized SCAN (rSCAN) and regularized-restored SCAN (r2SCAN) in combination with different perturbation orders, including phonon within harmonic approximation (HA) plus three- phonon scattering (HA+3ph), phonon calculated using self-consistent phonon theory (SCPH) plus three-phonon scattering (SCPH+3ph), and SCPH phonon plus three- and four-phonon scattering (SCPH+3,4ph). Our results show that the XC functional exhibits strong entanglement with perturbation order and the mean relative absolute error (MRAE) of the computed κL is strongly influenced by both the XC functional and perturbation order, leading to error cancellation or amplification. The minimal (maximal) MRAE is achieved with revTPSS (rSCAN) at the HA+3ph level, SCAN (r2SCAN) at the SCPH+3ph level, and PBEsol (rSCAN) at the SCPH+3,4ph level. Among these functionals, PBEsol exhibits the highest accuracy at the highest perturbation order. The SCAN- related functionals demonstrate moderate accuracy but are suffer from numerical instability and high computational costs. Furthermore, the different impacts of quartic anharmonicity on κL in rocksalt and zincblende structures are identified by all XC functionals, attributed to the distinct lattice anharmonicity in these two structures. These findings serve as a valuable reference for selecting appropriate functionals for describing anharmonic phonons and offer insights into high-order force constant calculations that could facilitate the development of more accurate XC functionals for solid materials.more » « less
