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:
- 10483958
- Publisher / Repository:
- Association for Computing Machinery
- Date Published:
- Journal Name:
- ACM Transactions on Graphics
- Volume:
- 42
- Issue:
- 4
- ISSN:
- 0730-0301
- Page Range / eLocation ID:
- 1 to 26
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
We prove that if G is the mapping torus group of an injective endomorphism of a free group (of possibly infinite rank), then every two‐generator subgroup H of G is either free or a (finitary) sub‐mapping torus. As an application we show that if phi is a fully irreducible atoroidal automorphism, then every two‐generator subgroup of of the mapping torus G of phi is either free or has finite index in G.more » « less
-
Lossy trapdoor functions, introduced by Peikert and Waters (STOC ’08), can be initialized in one of two indistinguishable modes: in injective mode, the function preserves all information about its input, and can be efficiently inverted given a trapdoor, while in lossy mode, the function loses some information about its input. Such functions have found countless applications in cryptography, and can be constructed from a variety of Cryptomania assumptions. In this work, we introduce targeted lossy functions (TLFs), which relax lossy trapdoor functions along two orthogonal dimensions. Firstly, they do not require an inversion trapdoor in injective mode. Secondly, the lossy mode of the function is initialized with some target input, and the function is only required to lose information about this particular target. The injective and lossy modes should be indistinguishable even given the target. We construct TLFs from Minicrypt assumptions, namely, injective pseudorandom generators, or even one-way functions under a natural relaxation of injectivity. We then generalize TLFs to incorporate branches, and construct all-injective-but-one and all-lossy-but-one variants. We show a wide variety of applications of targeted lossy functions. In several cases, we get the first Minicrypt constructions of primitives that were previously only known under Cryptomania assumptions. Our applications include: Pseudo-entropy functions from one-way functions. Deterministic leakage-resilient message-authentication codes and improved leakage-resilient symmetric-key encryption from one-way functions. Extractors for extractor-dependent sources from one-way functions. Selective-opening secure symmetric-key encryption from one-way functions. A new construction of CCA PKE from (exponentially secure) trapdoor functions and injective pseudorandom generators. We also discuss a fascinating connection to distributed point functions.more » « less
-
Sphere tracingis a fast and high-quality method for visualizing surfaces encoded by signed distance functions (SDFs). We introduce a similar method for a completely different class of surfaces encoded byharmonic functions, opening up rich new possibilities for visual computing. Our starting point is similar in spirit to sphere tracing: using conservativeHarnack boundson the growth of harmonic functions, we develop aHarnack tracingalgorithm for visualizing level sets of harmonic functions, including those that are angle-valued and exhibit singularities. The method takes much larger steps than naïve ray marching, avoids numerical issues common to generic root finding methods and, like sphere tracing, needs only perform pointwise evaluation of the function at each step. For many use cases, the method is fast enough to run real time in a shader program. We use it to visualize smooth surfaces directly from point clouds (via Poisson surface reconstruction) or polygon soup (via generalized winding numbers) without linear solves or mesh extraction. We also use it to visualize nonplanar polygons (possibly with holes), surfaces from architectural geometry, mesh exoskeletons, and key mathematical objects including knots, links, spherical harmonics, and Riemann surfaces. Finally we show that, at least in theory, Harnack tracing provides an alternative mechanism for visualizing arbitrary implicit surfaces.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- https://doi.org/10.1145/3592105
