Some of those fjords are 200+ meters deep at the narrowest points near the outlet, i.e. where you would want to build a bridge/tunnel/submerged tube.
We already use tunnel crossings underneath a lot of shallower crossings, and several not so shallow, like the one about half an hour south of Oslo, near Drøbak:
The tunnel is 7-8 km long even though the fjord is less than a km wide at that point, the extra distance was required in order to keep the incline at or below the (highway) maximum allowable 7%. The problem is that 3+ km of 7% downhill (requiring a lot of braking for a heavy rig) and then 3+ km of steep uphill is sufficient to cause trailer breakdowns more or less every week. We also get truck/bus fires inside tunnels almost every year here in Norway.
I am currently in the Hvaler archipelago on the south-east corner of Norway, a few km from the Swedish border. The main/only road leading to the largest of the many islands is nearly 4 km long and still needed 10% descent/ascent angles to get deep enough.
This is dangerous enough to force the entire tunnel to close down whenever a truck with dangerous/inflammable cargo (i.e. gasoline/LPG/diesel) needs to pass through.