Abstract This paper explores construction of gauge (diffeomorphism)-invariant observables in anti de Sitter (AdS) space and the related question of how to find a “holographic map” providing a quantum equivalence to a boundary theory. Observables are constructed perturbatively to leading order in the gravitational coupling by gravitationally dressing local field theory operators in order to solve the gravitational constraints. Many such dressings are allowed and two are explicitly examined, corresponding to a gravitational line and to a Coulomb field; these also reveal an apparent role for more general boundary conditions than considered previously. The observables obey a nonlocal algebra, and we derive explicit expressions for the boundary ...